Запуск
mvn compile
java -classpath target/classes ru.mmineev.osp.OspApp
Алгоритм А*
Ситуации хранятся в сортируемом списке
LinkedList<Action> rangedMoves = new LinkedList<>();Action - класс, хранящий текущее расположение фишек, путь и расстояние, и предыдущий ход.
Список сортируется по возрастанию функции сумма+стоимость
rangedMoves.sort(Comparator.comparing(Action::totalCost));Данная функция расчитывается следующим образом:
public int totalCost() {
return cost + distance;
}cost - стоимость пути, количество ходов
distance - расстояние до цсуммеели
Например для белых расстояние считается по такому распределению:
| 9 | 8 | 7 | ||
|---|---|---|---|---|
| 8 | 7 | 6 | ||
| 7 | 6 | 5 | 4 | 3 |
| 4 | 3 | 2 | ||
| 3 | 2 | 1 |
Для черных наоборот.
Программа берет первое значение в списке (с наименьшей суммой). Получает предполагаемые варианты ходов в список и затем сортирует его.
Делается 1000 вычислений, затем предлагается лучшее по стоимости пути решение. К моменту завершения оно оказывается окончательным.
Из оптимизаций было боработано вычисление расстояния. Ранее считалось, если фишка не на том месте, где должна быть +1 расстояние. В итоге программа гоняла фишки в середине так и не трогая самые дальние.
Новый метод "заставляет" загнать фишки как можно глубже в нужную половину