Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Отображение графа
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
SpLove SpLove вне форума
Member
 
Сообщений: 21
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.04.2005
По умолчанию 02.10.2006, 01:38

Найти путь между двумя вершинами в ненагруженном графе. Задача простая, я решил её так
Код:
/************************************************
* Program:    lab #2                *
* Description:    Find all ways between         *
*        two vertexs in unloaded graph    *
*************************************************/

%trace

DOMAINS
    list = symbol*.

PREDICATES
    /* Additional predicates*/
    add_arc(symbol, symbol).
    add_arc_ex(symbol, symbol).
    member(symbol, list).
    add_vertex(symbol, list, list).

    /* Primary predicates*/
    define_vertexs(symbol, symbol).
    find_way(symbol, symbol, list).

CLAUSES
    /* Create unloaded graph */
    /* Add new add_arcs */ 
    add_arc(V1,V2).
    add_arc(V1,V3).
    add_arc(V2,V4).
    add_arc(V3,V4).
    add_arc(V3,V5).
    add_arc(V4,V6).
    add_arc(V5,V6).
 
    /* Extend ways */
    add_arc(T2, T1).    
    add_arc_ex(T1, T2) :- add_arc(T1, T2).

    /* Find vertex in list */
    member(V1, [V1|_]).
    member(V1, [_|T]) :- member(V1,T). 

    /* Define begin and end vertex */
    define_vertexs(A, A).
    define_vertexs(A, B) :-
        write("Enter begin vertex : "),
        readln(A), nl, 
        write("Enter end vertex : "),
        readln(B). 

    /* Add vertex to find way */
    add_vertex(V, L, [V|L]).

    /* Find way between two vertexs */
    find_way(X, Y, L1) :- add_arc_ex(X, Y),
        not(member(Y, L1)),/* ATTENTION !!!!!!!!!!!!!!!!!!!!!!!!!! */
        add_vertex(Y, L1, L2),
        write(L2),nl,
        fail.
    find_way(X, Y, L1) :- add_arc_ex(X, W),
        not(member(W, L1)),
        find_way(W, Y, [W|L1]).
    
GOAL
    makewindow(1, 1, 1, "TEST", 0, 0, 25, 80),

    write("________________________________"), nl,    
    write("Finding all ways between two vertexs ... "), nl, nl,
    define_vertexs(Begin, End),

    write("Found way between vertex "),
    write(Begin),
    write(" and vertex "),
    write(End),
    write(" : "), nl,    
    find_way(Begin, End, Graph), nl,

    write("________________________________").
Правда в отмеченной строке выдает ошибку 704: Free variable are not allowed 'not' and 'retractall'. Как исправить? Еще очень интересует возможность позволить пользователю создавать граф указывая дуги и затем его отобразить в строку парами, например ((1, 2), (2, 3), ..., (4,6)). Как это можно сделать минимально изменив код???
Ответить с цитированием
  (#2 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 02.10.2006, 11:24

Попытайтесь сначала исправить глюки. Например, в этом месте:
Код:
add_arc(T2, T1).    
add_arc_ex(T1, T2) :- add_arc(T1, T2).
Потом, непонятен смысл вот этой строчки:
Код:
define_vertexs(A, A).
Судя по использованию предиката, аргументы там должны быть выходные, при этом не написано, чему равно значение A.
Цитата:
Правда в отмеченной строке выдает ошибку 704: Free variable are not allowed 'not' and 'retractall'. Как исправить?
У Вас предикат find_way реализуется так, что третий аргумент у него входной, а выходного аргумента, собственно найденного пути, вообще нет. К тому же отсутствует условие окончания рекурсии.
А запускаться, в разделе goal, он по идее должен так:
Код:
find_way(Begin, End, [Begin], Graph)
И еще:
Код:
add_arc(V1,V2).
...
- это факты? Аргументы там - это конкретные вершины? Непонятно, почему там стоят переменные.
Ответить с цитированием
  (#3 (permalink)) Старый
SpLove SpLove вне форума
Member
 
Сообщений: 21
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.04.2005
По умолчанию 03.10.2006, 08:58

Исправил так
Код:
/************************************************
* Program:    lab #2                *
* Description:    Find all ways between         *
*        two vertexs in unloaded graph    *
*************************************************/

%trace

DOMAINS
    list = symbol*.

PREDICATES
    /* Additional predicates*/
    add_arc(symbol, symbol).
    add_arc_ex(symbol, symbol).
    member(symbol, list).
    add_vertex(symbol, list, list).

    /* Primary predicates*/
    define_vertexs(symbol, symbol).
    find_way(symbol, symbol, list).

CLAUSES
    /* Create unloaded graph */
    /* Add new add_arcs */ 
    add_arc(v1,v2).
    add_arc(v1,v3).
    add_arc(v2,v4).
    add_arc(v3,v4).
    add_arc(v3,v5).
    add_arc(v4,v6).
    add_arc(v5,v6).
 
    /* Extend ways */
    add_arc_ex(T1, T2) :- add_arc(T1, T2);
    add_arc(T2, T1).    

    /* Find vertex in list */
    member(V, [V|_]).
    member(V, [_|T]) :- member(V,T). 

    /* Define begin and end vertex */
    define_vertexs(A, B) :-
        write("Enter begin vertex : "),
        readln(A), 
        write("Enter end vertex : "),
        readln(B).

    /* Add vertex to find way */
    add_vertex(V, L, [V|L]).

    /* Find way between two vertexs */
    find_way(X, Y, L1) :- add_arc_ex(X, Y),
        not(member(Y, L1)),
        add_vertex(Y, L1, L2),
        write(L2),nl,
        fail.
    find_way(X, Y, L1) :- add_arc_ex(X, W),
        not(member(W, L1)),
        find_way(W, Y, [W|L1]).
    
GOAL
    makewindow(1, 10, 2, "2ECOND.PRO", 0, 0, 25, 80),

    write("________________________________________"), nl,    
    write("Finding all ways between two vertexs ... "), nl, nl,
    define_vertexs(Begin, End),

    write("Found way between vertex "),
    write(Begin),
    write(" and vertex "),
    write(End), nl,    
    find_way(End, Begin, [End]), nl,
    
    write("_______________________________________").
add_arc_ex - для того что бы если например из вершины 1 можно попасть в вершину 2, то можно было бы и из 2 в первую. Т. е. делаем дуги направлеными в обе стороны. Жаль на вопрос о представлении не ответили :-(
Ответить с цитированием
  (#4 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 03.10.2006, 20:44

Цитата:
Жаль на вопрос о представлении не ответили
Сначала нужно с ошибками разобраться.
Кстати, не иметь выходного аргумента для предиката, который находит путь - не очень хорошо.
Цитата:
Еще очень интересует возможность позволить пользователю создавать граф указывая дуги и затем его отобразить в строку парами, например ((1, 2), (2, 3), ..., (4,6)). Как это можно сделать минимально изменив код???
Проще всего объявить предикат add_arc не в разделе predicates, а в разделе database. Ну а затем добавить ввод и вывод графа, например, так:
Код:
input_graf:- define_vertexs(A, B), !, assert(add_arc(A,B)), input_graf.
input_graf.

output_graf:- write("("), add_arc(A,B), writef("(%, %) ", A, B), fail; write(")").
Ответить с цитированием
Ads
Ответ

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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
ребро связности графа imported_Catherine Prolog 1 25.04.2011 22:30
деревянное покрытие графа imported_r2d2 Prolog 5 13.01.2009 19:22
планарность графа SunnyA Форум программистов 0 24.05.2008 02:46
к-связность графа nigyl Pascal 1 05.06.2007 14:55
1-база графа imported_Andr Prolog 3 24.12.2006 17:29
Определение графа AntonZima Prolog 8 22.11.2006 16:29
Связанность графа _KisA_ Prolog 10 23.10.2006 11:39
Связность графа на swi. imported_director Prolog 4 06.09.2005 16:09
Диаметр графа hamster Prolog 5 18.05.2005 18:54
Компоненты связности графа JohnyJO Prolog 2 16.05.2005 10:21
раскраска графа Liya Prolog 9 01.02.2005 01:04
Планарность графа linux Prolog 1 12.12.2004 22:43



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