Дейкстра алгоритмімен шешілетін есепке сипаттама беріңіз. Алгоритмді қолданып жалпылама мысал келтіріңіз.

Бұ л алгоритм графтың барлық тө белері мен ұ зындық тары арасында ең қ ысқ а жолды табады. Графтың белгілі бір тө бесі мен басқ а тө белері арасындағ ы оптималды маршрутты табатын Дейкстра алгоритмінің жұ мыс істеу принципін қ арастырайық. Мысал ү шін келесі G графын алайық:

Бұ л графты келесі С матрицасы тү рінде жазуғ а болады:

Басты тө бе ретінде 1-тө бені алайық. Бұ л 1-тө беден басқ а 2, 3, 4, 5-тө белерге ең қ ысқ а жолды іздейтінімізді білдіреді. Бұ л алгоритм графтың барлық тө белеріне қ адаммен барып, басты тө беден белгілі бір тө беге дейінгі ең минималды қ ашық тық ты білдіретін жолғ а белгі қ ойып отырады.

1-тө беге басты тө бе болғ андық тан 0 белгісін қ оямыз. Қ алғ ан тө белерге шексіздік белгісін қ оямыз.

Минималды белгіге ие болатын тө бені (W) деп белгілейміз (қ азір ол 1-тө бе), жә не W-тө беден тікелей жол бар басқ а тө белерді қ арастырамыз. W-тө бесі мен келесі тө бе қ ашық тығ ының суммасын тауып, алынғ ан мә н қ арастырылғ ан тө бенің мә нінен кіші болса оны осы мә нмен ауыстырамыз. Егер сумма кіші болмаса алдың ғ ы белгіні ө згертусіз қ алдырамыз.

W-тө беден тікелей жол бар басқ а тө белерді қ арастырып болғ ан соң, W-тө бені қ арастырылғ ан тө бе ретінде белгілейміз. Енді ә лі қ арастырылмағ ан тө белердің ішінен белгі мә ні ең минималды тө бені таң дап аламыз, бұ л біздің келесі W-тө беміз болады. Қ азір бұ л тө бе 2 немесе 5. Егер белгілері бірдей бірнеше тө бе бар болса, W-тө бе ретінде олардың кез-келгенін ала беруге болады. Біз 2-тө бесін алайық. Бірақ одан шығ атын бірде-бір тө бе болмағ андық тан оны бірден қ арастырылғ ан тө бе ретінде белгілейміз де, келесі минималды белгісі бар тө беге кө шеміз. Бұ л жолы тек 5-тө бесі минималды мә нге ие. 5-тө бесінен шығ атын тікелей қ атынайтын жол бар тө белерді қ арастырамыз, бірақ ә лі қ арастырылғ ан тө бе ретінде белгіленбеген тө белерді ғ ана. Тағ ы да W-тө бесінің белгісі мен белгілі бір тө беге дейінгі қ абырғ а суммасын табамыз. Егер бұ л сумма алдың ғ ы белгіден аз болса, онда белгінің мә нін алынғ ан суммағ а ө згертеміз.

Суреттен 3 жә не 4 тө белерінің мә ндері азайғ анын кө реміз. Демек, негізгі тө беден бұ л тө белерге дейінгі ә лдеқ айда қ ысқ а маршрут табылды. Енді 5-тө бені қ арастырылғ ан тө бе ретінде белгілеп, келесі минималды мә нге ие тө беге кө шеміз. Барлық тө белерді қ арастырып болғ анша жоғ арыда айтылғ ан ә рекеттерді қ айталаймыз.

Барлық ә рекеттерді орындай келе келесідей нә тиже аламыз:

3) Логикалық программалау туралы жалпы сипаттама берінің із. Логикалық программалаудың бір тілін толық сипаттаң ыз.

ЕЯ-дан формальдық ЛП тіліне ө ту формализаця деп аталады. Бұ л процесс интерпретация процесына қ айшы.Нә тижеде формализация ЕЯ-дағ ы фраза ППФ ЛП-ғ а сә йкес қ ойылады. Мысалы, (высказывание) «егер 2 кезкелген объектілер (х жә не у) тең, онд аолар бірдей қ асиетке ие болады» қ арастырайық. ЛП тілінде бұ л фразаны былай қ арастыруғ а болады: (РАВНО () ())

Бұ л ө рнек ЛП 1-ші ретті формула болмайды, у квантифицируется предикат Р. (Р(х) – х –Р қ асиетінеие).ЛП формуласын келесі тү рде орнектейік:

Егер оның қ анаты болса, ол – қ ұ с.

Егер олұ шса жә не жұ мыртқ абасса, ол – қ ұ с.

ЛП тіліне ө ту ү шін х айнымалысын енгіземіз, Кө пшілік тірі жандардың қ асиетін қ абылдайтын. Бір орынды предикаттарды енгізіміз – қ асиеті.

Қ АНАТЫБАР(х),

Ұ ШАДЫ(х),

ЖҰ МЫРТҚ А БАСАДЫ(х),

Қ Ұ С(х).

Соң ғ ы предикат тірі жанның қ асиетін сипаттайды х қ ұ с болады. Соң ында формулаларды осылай қ оямыз:

Қ АНАТЫБАР(х) Қ Ұ С(х),

Ұ ШАДЫ(х) ЖҰ МЫРТҚ А БАСАДЫ(х) Қ Ұ С(х).

Егер х=Синица, онда бұ л импликациялар И, егер х=Қ оян, то – Л.

Мұ нда Синица, Қ оян – объект тілі константталар(кө пшілік тірі жандар элементтері).

ЛП, ЛВ сияқ ты, интеллектуальдық есептерді шешу ү шін қ олданылады.