помогите с алгоритмом

  • Автор темы nobody
  • Дата начала
N

nobody

#1
может єто вопрос и не от крутого програмера... но ...
есть такая задача
Задано целевую позиции в игре, имеет следующие правила:
- Шашку можно передвигать на соседнее поле;
- Разрешается переступать через соседнюю шашку, если за ней есть свободное поле; - белые и черные шашки должны продвигаться навстречу без возвратов назад.
Необходимо превратить начальную позицию на целевую.
т.е. 1110222 -> 2220111
мне ее надо решить оптимальным способом, то есть не перебирая все возможные варианты. Нужно оценить каждую вершину графа и выбрать оптимальный
вот например ......
1110222 (раскроем сначала вершину по правилам)
1101222 1011222 1112022 1112202
я пробовал делать так ... какая вершина имеет больше способов раскрыться ту и раскрывал .... если же таких вершин две то раскрывал обе .....
здесь первую и третью вершины (1101222 и 1112022) можно раскрыть тремя способами, вот я их и раскрыл. так я действовал и далее .... этот способ действовал пока я почти не дошел конца ... здесь я получил две вершины
1212120 1212012
по моему алгоритму вторая вершина можно раскрыть двумя способами а первую только одним (т.е. первая вообще отвергается ).... но как оказалось к правильному ответу приводит именно первая вершина .. а вторая ведет в тупик ...... я долго мучился но так ничего и не придумал ...
говоря о раскрытии разными способами я говорю о правилах которые написаны в условии задачи ......
мне НЕ нужно чтобы кто то писал мне программу ... это все я и сам сделаю .... просто подскажите алгоритм ...
 
14.09.2010
5
0
#2
Базовых правил четыре: 10 => 01, 02 => 20, 120 => 021, 012 => 210.
Очевидно, что надо как-то оценивать то, что слева и справа от нуля.
Например, ситуации 0..11 и 22..0 кажется тупиковые.
 
N

nobody

#3
я придумал один алгоритм.... это конечно не сильно заумный алгоритм но тем не менее он дейстует.. и еще за результатами оценочной ф-ии просматривать нужно максимум две вершины (это при условии 3-ех шашек одного цвета... тоесть 7 цифр)..
и так....
я по прежему оцениваю количество вершин на которые можно разбить текущею... (тоесть первую можно разбить на 4, какую то следующею можно на 3 и т.д....) но... я емпирически заметил (это типа методом проб и ошибок, но звучит как то круче))) что вершина хуже если у нее одинаковые цифры стоят рядом(тоесть 0122211 или 2211021) и наоборот, если цифри идут по очереди то такая вершина круче..... и я до сумы возможной разбивки добавляю количество цифр 12 которые идут рядышком (тоесть 1212022 -> 3(на это количество вершин можно разбить ЭТУ вершину) + 2(количество цифр 12)) тоесть за этим (так сказать ) алгоритмом число 1212120 выигрывает по стравнению с числом 1212012....
я понимаю это фуфло по сравнению с (может быть) таким, например, алгоритмом как метод ветвей.. но как ни как(нееееее........ "как-ни-как" это не запор :rolleyes: ) работает