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

Тема в разделе "Другие", создана пользователем nobody, 6 ноя 2010.

  1. nobody

    nobody Гость

    может єто вопрос и не от крутого програмера... но ...
    есть такая задача
    Задано целевую позиции в игре, имеет следующие правила:
    - Шашку можно передвигать на соседнее поле;
    - Разрешается переступать через соседнюю шашку, если за ней есть свободное поле; - белые и черные шашки должны продвигаться навстречу без возвратов назад.
    Необходимо превратить начальную позицию на целевую.
    т.е. 1110222 -> 2220111
    мне ее надо решить оптимальным способом, то есть не перебирая все возможные варианты. Нужно оценить каждую вершину графа и выбрать оптимальный
    вот например ......
    1110222 (раскроем сначала вершину по правилам)
    1101222 1011222 1112022 1112202
    я пробовал делать так ... какая вершина имеет больше способов раскрыться ту и раскрывал .... если же таких вершин две то раскрывал обе .....
    здесь первую и третью вершины (1101222 и 1112022) можно раскрыть тремя способами, вот я их и раскрыл. так я действовал и далее .... этот способ действовал пока я почти не дошел конца ... здесь я получил две вершины
    1212120 1212012
    по моему алгоритму вторая вершина можно раскрыть двумя способами а первую только одним (т.е. первая вообще отвергается ).... но как оказалось к правильному ответу приводит именно первая вершина .. а вторая ведет в тупик ...... я долго мучился но так ничего и не придумал ...
    говоря о раскрытии разными способами я говорю о правилах которые написаны в условии задачи ......
    мне НЕ нужно чтобы кто то писал мне программу ... это все я и сам сделаю .... просто подскажите алгоритм ...
     
  2. Вождь

    Вождь Member

    Регистрация:
    14 сен 2010
    Сообщения:
    5
    Симпатии:
    0
    Базовых правил четыре: 10 => 01, 02 => 20, 120 => 021, 012 => 210.
    Очевидно, что надо как-то оценивать то, что слева и справа от нуля.
    Например, ситуации 0..11 и 22..0 кажется тупиковые.
     
  3. nobody

    nobody Гость

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

Поделиться этой страницей