Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Проблемы при эвристическом поиске.
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
iosin iosin вне форума
Новичок
 
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 09.10.2005
По умолчанию Проблемы при эвристическом поиске. - 24.10.2005, 00:24

Здравствуйте,

Помогите пожалуйста разобраться с моей программой.
Задача поменять все черные шашки с белыми, можно перепрыгивать.
Наверное, программа написано коряво, но все же почти работает.

Код:
main(Path):-
    init(State),
    best_first([1000-s(State,[])],[],[],Path).


% + Текущий фронт, +Следующий фронт, +История, -Конечный путь
best_first([0-s(State,Path)|_], _, _, Path).
best_first([_-s(State,Path)|Fr], NextFr, History, EndPath):-
    find_empty(State, Ie, Je),
    findall(M/StateI, move(State, StateI, Ie, Je, M),Ms),
    next_fr_add(Ms, NextFr, NextFr1, History, Path),
    history_add(State1, History, History1),
                best_first(Fr, NextFr1, History1, EndPath).
best_first([],[],_,_):-        
    !,
    fail.
best_first([],NextFr,History,EndPath):-       
    sort(NextFr, NextFr1),
    best_first(NextFr1,[],History,EndPath).

% Оцениваем вершину и добавляем в следующий фронт
next_fr_add([Move/State1|Ms], NextFr, [Val-s(State1, [Move|Path])|NextFr1], History,Path):-
    not( member(History,State1)),
    eval( State1, Val),
    !,
    next_fr_add(Ms,NextFr,NextFr1,History,Path).

next_fr_add([_|Ms],NextFr,NextFr1,History,Path):-                              
    next_fr_add(Ms,NextFr,NextFr1,History,Path).
next_fr_add([],NextFr,NextFr,_,_).

history_add(State,History,History):-
    finish(State), 
    !.
history_add(State,History,[State|History]).

init([ b(1,3,b), b(2,3,b), 
        b(1,2,b), b(2,2,e), b(3,2,w),  
                     b(2,1,w), b(3,1,w)]).
finish([ b(1,3,w), b(2,3,w), 
           b(1,2,w), b(2,2,e), b(3,2,b),  
                         b(2,1,b), b(3,1,b)]).

% Оценочная функция, оценивает нормально, испытывал.
eval( State, E):-
    findall(I-J, member(b(I,J,w), State), Lw),
    eval_whites(Lw, 0, Ew),
    findall(I-J, member(b(I,J,b), State), Lb),
    eval_blacks(Lb, 0, Eb),
    E is Ew+Eb-10.

eval_whites([], Rv, Rv).
eval_whites([I-J|Lw], Cv, Rv):-     /* I->1,   J->3 */
    J1 is 3 - J,
    Cv1 is Cv + I + J1,
    eval_whites(Lw, Cv1, Rv).

eval_blacks([], Rv, Rv).
eval_blacks([I-J|Lw], Cv, Rv):-     /* I->3,   J->1 */
    I1 is 3 - I,
    Cv1 is Cv + J + I1,
    eval_blacks(Lw, Cv1, Rv).
    
test(1,E):-
    init(C),
    eval(C, E).
test(2,E):-
    finish(C),
    eval(C, E).

find_empty( C, I, J):-
    member(b( I, J, e), C),!.

move( C, C2, Ie, Je, kk):-  
    Ie1 is Ie+1,
    member( b(Ie1, Je, X), C),
    set( b(Ie1,Je,X), b(Ie1,Je,e), C, C1),
    set( b(Ie,Je,e), b(Ie,Je,X), C1, C2).
move( C, C2, Ie, Je, kk):-       
    Ie1 is Ie+2,
    member( b(Ie1, Je, X), C),
    set( b(Ie1,Je,X), b(Ie1,Je,e), C, C1),
    set( b(Ie,Je,e), b(Ie,Je,X), C1, C2).
move( C, C2, Ie, Je, kk):-       
    Je1 is Je-1,
    member( b(Ie, Je1, X), C),
    set( b(Ie,Je1,X), b(Ie,Je1,e), C, C1),
    set( b(Ie,Je,e), b(Ie,Je,X), C1, C2).
move( C, C2, Ie, Je, kk):-       
    Je1 is Je-2,
    member( b(Ie, Je1, X), C),
    set( b(Ie,Je1,X), b(Ie,Je1,e), C, C1),
    set( b(Ie,Je,e), b(Ie,Je,X), C1, C2).
move( C, C2, Ie, Je, kk):-   
    Ie1 is Ie-1,
    member( b(Ie1, Je, X), C),
    set( b(Ie1,Je,X), b(Ie1,Je,e), C, C1),
    set( b(Ie,Je,e), b(Ie,Je,X), C1, C2).
move( C, C2, Ie, Je, kk):-      
    Ie1 is Ie-2,
    member( b(Ie1, Je, X), C),
    set( b(Ie1,Je,X), b(Ie1,Je,e), C, C1),
    set( b(Ie,Je,e), b(Ie,Je,X), C1, C2).
move( C, C2, Ie, Je, kk):-      
    Je1 is Je+1,
    member( b(Ie, Je1, X), C),
    set( b(Ie,Je1,X), b(Ie,Je1,e), C, C1),
    set( b(Ie,Je,e), b(Ie,Je,X), C1, C2).
move( C, C2, Ie, Je, kk):-      
    Je1 is Je+2,
    member( b(Ie, Je1, X), C),
    set( b(Ie,Je1,X), b(Ie,Je1,e), C, C1),
    set( b(Ie,Je,e), b(Ie,Je,X), C1, C2).

set( X, Xnew, [X|Xs], [Xnew|Xs]).
set( X, Xnew, [Y|Xs], [Y|Lnew]):- set( X, Xnew, Xs, Lnew).
Метод "сначала лучший", работает быстро. Но это, если все ходы обозначены как "кк", а если каждый ход идентифицировать как пологается, то ... не хватает стека. Даже если хотя бы название одного ходя поменять, к примеру, на кк1, то счета не получится...
(Название хода - последний параметр в предикате move)

Подскажите пожалуйста, с чем это связано, что можно сделать, и может быть мне следут использовать другой метод поиска?

Заранее благодарен.
Ответить с цитированием
  (#2 (permalink)) Старый
iosin iosin вне форума
Новичок
 
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 09.10.2005
По умолчанию 24.10.2005, 00:27

b - черная шашка, w - белая, e - пустое поле.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Проблемы с HDD Юрасик Накопители 8 18.02.2012 14:29
Нужна помощь в поиске программиста Lamari Вопросы начинающих программистов 2 06.12.2011 12:54
Проблемы с WTK и SDK cgw J2ME 0 27.10.2011 17:41
Как сделать так чтобы при поиске в бд выделялась вся строка vlad_titov C++ Builder 0 11.06.2011 20:59
Операция срвванния при поиске нужного документа в С++ Alex_Jan Вопросы начинающих программистов 9 07.06.2009 13:51
Проблемы с новым компьютером, в играх зависает и другие проблемы. Djekpot Техническая поддержка 6 25.02.2009 04:43
SQL 30082 При чтении или поиске C-записи достигнут конец файла Voin Другие СУБД 5 25.07.2008 14:18
Задача о графе( в поиске не нашел ответа) Agregad Prolog 4 15.06.2008 20:50
Применение функции strstr в поиске заданных слов Аринка Вопросы начинающих программистов 4 18.12.2007 04:36
А есть топик по фотошопу? Я в поиске не нашел. Может пора создать? Woodpecker monitor Графика & дизайн 34 01.08.2007 12:29
Как осуществить алгоритм заполнения ProgressBar при поиске файлов lexey Delphi 6 04.11.2004 11:45



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов