Все технические форумы на одном сайте Удобный поиск информации с популярных форумов в одном месте
Вопрос: Обзор алгоритмов сжатия

Пролог
-----------------


Однажды понадобилось мне зашить внешний файл в свою программу, чтобы он не таскал везде свою задницу вместе с исполняемым файлом. Я сделал это через команду "INCBIN" (для фасма FILE), но на выходе получил исполняемый файл неимоверных размеров. Тогда возникла идея прошить в программу упакованый/внешний файл, но для этого нужно было добавить в программу ещё и декодер, который распаковал-бы его. Готовые пакеры не подходили мне тем, что я не знал алгоритмов по которому они пакуют, и пришлось писать свой архиватор.

За время поисков набрал кучу инфы по этой теме, с которой хотелось-бы поделиться с Вами. Статья расчитана на тех, кто хотел-бы освоить тему сжатия информации, но уровень знаний не позволяет им самостоятельно разобраться в куче математических формул и непонятных терминов. Не знаю: правильно я понял всё/это или нет, но главное - положительный результат, который в данном случае я получил. Буду использовать FASM, редактор HxD, ну и виндовый CALC в инженерном виде.


Введение
-----------------


Характерной особенностью данных является их избыточность. Причём эта избыточность проявляется у всех типов данных, будь то битовый поток или разговорная речь. В надежде донести до собеседника свою мысль, мы невольно повторяем одинаковые слова и это оправдано. Избыточность улучшает восприятие информации. Однако, когда речь идёт о хранении и передаче инфы средствами компьютерной техники, избыточность играет отрицательную роль, повышая стоимость хранения данных.

Степень избыточности привязана к типу данных:
Код
............ 1. Видео - максимальная избыточность;
---------------------------------------------------------------------------
00006960  2F 00 00 00 01 00 00 0E A9 00 00 00 01 00 00 0E  /.......©.......
00006970  AA 00 00 00 01 00 00 0E A9 00 00 00 03 00 00 0E  Є.......©.......
00006980  AA 00 00 00 01 00 00 0E A9 00 00 00 03 00 00 0E  Є.......©.......
00006990  AA 00 00 00 01 00 00 0E A9 00 00 00 03 00 00 0E  Є.......©.......

............ 2. Графика - средняя избыточность;
---------------------------------------------------------------------------
00007C30  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя
00007C40  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя
00007C50  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя
00007C60  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя

............ 3. Текст - минимальная избыточность;
---------------------------------------------------------------------------
00000000  CB E5 EE ED E8 E4 20 D4 E8 EB E0 F2 EE E2 2E 20  Леонид Филатов. 
00000010  CF F0 EE 20 D4 E5 E4 EE F2 E0 2D F1 F2 F0 E5 EB  Про Федота-стрел
00000020  FC F6 E0 20 09 0D 0A D1 CA C0 C7 CA C0 20 C4 CB  ьца ...СКАЗКА ДЛ
00000030  DF 20 D2 C5 C0 D2 D0 C0 20 0D 0A 0D 0A 20 20 20  Я ТЕАТРА ....
Очевидно, что для сжатия разных типов информации нужны и разные алгоритмы сжатия. К примеру, у видео- и графики просматриваются цепочки повторяющихся байт, которые можно закодировать в формате "Байт->Повторов", хотя с текстом такой фокус уже не пройдёт.

Весь зоопарк алгоритмов сжатия можно разделить на три группы, которые принципиально отличаются друг-от-друга. В реальных условиях, эти алгоритмы комбинируются для получения универсальных пакеров:

- Алгоритм "RLE" (Run-Length-Encoding);
- Алгоритм "LZ" (Лемпеля-Зива);
- Алгоритм "Хаффмана".

Для всех систем сжатия требуется 2 алгоритма: компрессии на стороне источника, и декомпрессии у её получателя. Обычно, эти алгоритмы ассиметричны во-времени, т.к. алгоритм кодирования имеет право быть довольно медленным, в то время как декодер должен быть быстрым, чтобы удовлетворять требованиям пользователя. Рассмотрим в двух-словах основные различия этих алгоритмов.

Алгоритм RLE:
^^^^^^^^^^^^^^^^^^^^

- Кодирование цепочек одинаковых байт.
Для этой цели применяют байт-маркеры. Цепочки не одинаковых байт, вообще никак не кодируются, и передаются в открытом виде. К примеру, маркер [09h,38h] заставит декодер отправить на выход 9 восьмёрок, и т.д. Алгоритм даёт хорошие результаты при кодировании видео- и графики.


Алгоритм LZ:
^^^^^^^^^^^^^^^^^^^^

- Кодирование лексических единиц и помещение их в словарь.
За основу взят принцип поиска подстроки-в-строке. Алгоритм имеет буфер, который разделён на две/неравные части. Первая часть представляет из себя собственно буфер данных, а вторая часть - словарь алгоритма. Входной поток читается в буфер (по образу бегущей строки влево), и содержимое буфера сравнивается со-словарём. Каждая фраза словаря кодируется в байт:

|------- Словарь ------|-- Буфер --|---<<---входной поток....

В этом алгоритме, процент сжатия пропорционален размеру словаря.
Так-как словарь нужно отправлять вместе с упакованым блоком данных, то приходится искать золотую середину: или уменьшить процент сжатия, или увеличить словарь. Алгоритм даёт хорошие результаты при кодировании больших объёмов данных, причём эти данные могут быть любого типа.


Алгоритм Хаффмана:
^^^^^^^^^^^^^^^^^^^^

- Кодирование в виде бинарного древа.
Хаффман пошёл совсем иным путём, и решил съэкономить не то-что на каждом байте, а даже на каждом его бите. Кодер начинает работу с того, что сканирует сразу весь файл, и подсчитывает в нём кол-во вхождений каждого из символов. Так он получает вес каждого байта во-входном потоке данных:

00000000 F0 E0 F1 F1 EC EE F2 F0 E8 EC F1 F2 F0 EE EA F3 рассмотримстроку
--------+------------------------------------------------------------------
Байт | Вес
--------+------
F0h (р) | 3
E0h (а) | 1
F1h (с) | 3
ECh (м) | 2
;....... и т.д.

Теперь, Хаффман сортирует эти веса по-убыванию, в результате чего самые часто/встречающиеся байты выстаиваются в начале древа, и кодируются всего одним битом. Наименее встречающиеся байты будут кодироваться наибольшей разрядной сеткой, за счёт чего возрастает процент сжатия. Для зрительного восприятия это можно представить так.., хотя на самом деле всё чуть/подругому:

вес: 7 6 5 4 3 2 1 0
бит: 0 1 2 3 4 5 6 7

По сути, определение "бинарное древо" здесь чуть неуместно. Правильнее было-бы сказать "бинарный корень", т.к. это древо растёт сверху-вниз. Все байты с тяжёлым весом занимают верхнии позиции в начале корня, и корень разрастается ветками в виде легковесных байтов - вниз. Для адреса самого лёгкого байта в древе (байт, который редко встречается в тексте и валяется внизу корня), нужно потратить больше бинарных единиц, но к нему и меньше всего обращений. Выигрыш - на лицо!

Тонкости алгоритма Хаффмана оставим на потом, а пока разберём детали каждого из алгоритмов сжатия, начиная с самого простого: Run-Len-Encoding.
Ответ:
Сообщение от Kukuxumushu
RLE ... примитивнейший алгоритм

Не по теме:

Это иллюзия :-) В то время, как Хаффман, математически, просто инвертор длин кодов (кодового дерева), RLE меняет размерность кодового пространства (сравните, например, с транслитом из кириллицы в латиницу).

И, к слову, +

Вопрос: Обзор алгоритмов сжатия

Пролог
-----------------


Однажды понадобилось мне зашить внешний файл в свою программу, чтобы он не таскал везде свою задницу вместе с исполняемым файлом. Я сделал это через команду "INCBIN" (для фасма FILE), но на выходе получил исполняемый файл неимоверных размеров. Тогда возникла идея прошить в программу упакованый/внешний файл, но для этого нужно было добавить в программу ещё и декодер, который распаковал-бы его. Готовые пакеры не подходили мне тем, что я не знал алгоритмов по которому они пакуют, и пришлось писать свой архиватор.

За время поисков набрал кучу инфы по этой теме, с которой хотелось-бы поделиться с Вами. Статья расчитана на тех, кто хотел-бы освоить тему сжатия информации, но уровень знаний не позволяет им самостоятельно разобраться в куче математических формул и непонятных терминов. Не знаю: правильно я понял всё/это или нет, но главное - положительный результат, который в данном случае я получил. Буду использовать FASM, редактор HxD, ну и виндовый CALC в инженерном виде.


Введение
-----------------


Характерной особенностью данных является их избыточность. Причём эта избыточность проявляется у всех типов данных, будь то битовый поток или разговорная речь. В надежде донести до собеседника свою мысль, мы невольно повторяем одинаковые слова и это оправдано. Избыточность улучшает восприятие информации. Однако, когда речь идёт о хранении и передаче инфы средствами компьютерной техники, избыточность играет отрицательную роль, повышая стоимость хранения данных.

Степень избыточности привязана к типу данных:
Код
............ 1. Видео - максимальная избыточность;
---------------------------------------------------------------------------
00006960  2F 00 00 00 01 00 00 0E A9 00 00 00 01 00 00 0E  /.......©.......
00006970  AA 00 00 00 01 00 00 0E A9 00 00 00 03 00 00 0E  Є.......©.......
00006980  AA 00 00 00 01 00 00 0E A9 00 00 00 03 00 00 0E  Є.......©.......
00006990  AA 00 00 00 01 00 00 0E A9 00 00 00 03 00 00 0E  Є.......©.......

............ 2. Графика - средняя избыточность;
---------------------------------------------------------------------------
00007C30  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя
00007C40  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя
00007C50  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя
00007C60  DB FF 81 FF 81 FF 91 FF 81 FF 81 FF 91 FF 81 FF  ЫяЃяЃя‘яЃяЃя‘яЃя

............ 3. Текст - минимальная избыточность;
---------------------------------------------------------------------------
00000000  CB E5 EE ED E8 E4 20 D4 E8 EB E0 F2 EE E2 2E 20  Леонид Филатов. 
00000010  CF F0 EE 20 D4 E5 E4 EE F2 E0 2D F1 F2 F0 E5 EB  Про Федота-стрел
00000020  FC F6 E0 20 09 0D 0A D1 CA C0 C7 CA C0 20 C4 CB  ьца ...СКАЗКА ДЛ
00000030  DF 20 D2 C5 C0 D2 D0 C0 20 0D 0A 0D 0A 20 20 20  Я ТЕАТРА ....
Очевидно, что для сжатия разных типов информации нужны и разные алгоритмы сжатия. К примеру, у видео- и графики просматриваются цепочки повторяющихся байт, которые можно закодировать в формате "Байт->Повторов", хотя с текстом такой фокус уже не пройдёт.

Весь зоопарк алгоритмов сжатия можно разделить на три группы, которые принципиально отличаются друг-от-друга. В реальных условиях, эти алгоритмы комбинируются для получения универсальных пакеров:

- Алгоритм "RLE" (Run-Length-Encoding);
- Алгоритм "LZ" (Лемпеля-Зива);
- Алгоритм "Хаффмана".

Для всех систем сжатия требуется 2 алгоритма: компрессии на стороне источника, и декомпрессии у её получателя. Обычно, эти алгоритмы ассиметричны во-времени, т.к. алгоритм кодирования имеет право быть довольно медленным, в то время как декодер должен быть быстрым, чтобы удовлетворять требованиям пользователя. Рассмотрим в двух-словах основные различия этих алгоритмов.

Алгоритм RLE:
^^^^^^^^^^^^^^^^^^^^

- Кодирование цепочек одинаковых байт.
Для этой цели применяют байт-маркеры. Цепочки не одинаковых байт, вообще никак не кодируются, и передаются в открытом виде. К примеру, маркер [09h,38h] заставит декодер отправить на выход 9 восьмёрок, и т.д. Алгоритм даёт хорошие результаты при кодировании видео- и графики.


Алгоритм LZ:
^^^^^^^^^^^^^^^^^^^^

- Кодирование лексических единиц и помещение их в словарь.
За основу взят принцип поиска подстроки-в-строке. Алгоритм имеет буфер, который разделён на две/неравные части. Первая часть представляет из себя собственно буфер данных, а вторая часть - словарь алгоритма. Входной поток читается в буфер (по образу бегущей строки влево), и содержимое буфера сравнивается со-словарём. Каждая фраза словаря кодируется в байт:

|------- Словарь ------|-- Буфер --|---<<---входной поток....

В этом алгоритме, процент сжатия пропорционален размеру словаря.
Так-как словарь нужно отправлять вместе с упакованым блоком данных, то приходится искать золотую середину: или уменьшить процент сжатия, или увеличить словарь. Алгоритм даёт хорошие результаты при кодировании больших объёмов данных, причём эти данные могут быть любого типа.


Алгоритм Хаффмана:
^^^^^^^^^^^^^^^^^^^^

- Кодирование в виде бинарного древа.
Хаффман пошёл совсем иным путём, и решил съэкономить не то-что на каждом байте, а даже на каждом его бите. Кодер начинает работу с того, что сканирует сразу весь файл, и подсчитывает в нём кол-во вхождений каждого из символов. Так он получает вес каждого байта во-входном потоке данных:

00000000 F0 E0 F1 F1 EC EE F2 F0 E8 EC F1 F2 F0 EE EA F3 рассмотримстроку
--------+------------------------------------------------------------------
Байт | Вес
--------+------
F0h (р) | 3
E0h (а) | 1
F1h (с) | 3
ECh (м) | 2
;....... и т.д.

Теперь, Хаффман сортирует эти веса по-убыванию, в результате чего самые часто/встречающиеся байты выстаиваются в начале древа, и кодируются всего одним битом. Наименее встречающиеся байты будут кодироваться наибольшей разрядной сеткой, за счёт чего возрастает процент сжатия. Для зрительного восприятия это можно представить так.., хотя на самом деле всё чуть/подругому:

вес: 7 6 5 4 3 2 1 0
бит: 0 1 2 3 4 5 6 7

По сути, определение "бинарное древо" здесь чуть неуместно. Правильнее было-бы сказать "бинарный корень", т.к. это древо растёт сверху-вниз. Все байты с тяжёлым весом занимают верхнии позиции в начале корня, и корень разрастается ветками в виде легковесных байтов - вниз. Для адреса самого лёгкого байта в древе (байт, который редко встречается в тексте и валяется внизу корня), нужно потратить больше бинарных единиц, но к нему и меньше всего обращений. Выигрыш - на лицо!

Тонкости алгоритма Хаффмана оставим на потом, а пока разберём детали каждого из алгоритмов сжатия, начиная с самого простого: Run-Len-Encoding.
Ответ:
Сообщение от Kukuxumushu
RLE ... примитивнейший алгоритм

Не по теме:

Это иллюзия :-) В то время, как Хаффман, математически, просто инвертор длин кодов (кодового дерева), RLE меняет размерность кодового пространства (сравните, например, с транслитом из кириллицы в латиницу).

И, к слову, +

Вопрос: Как произвести вращение вокруг локальной оси, если система координат задана матрицей поворота?

Есть локальная координатная система, которая задана одной матрицей поворота 3x3. Пространство трёхмерное.
Чтобы получить координаты точки в этой системе, точка представляется как матрица-столбец (с координатами из глобальной системы) и умножается на матрицу поворота. Также известны углы поворота вокруг глобальных осей для преобразования глобальной системы координат в локальную.

Как можно вращать локальную координатную систему вокруг своих осей? Удобно было бы составить новую матрицу поворота вокруг локальной оси, на которую можно было бы умножать изначальную матрицу поворота.
Ответ:
Сообщение от andreysv
Пока линейную алгебру "знаю" так, что не понимаю толком, почему матрица поворота правильно трансформирует точку.
Вообще, если обобщенно - матрица трансформации это матрица перехода от одного базиса к другому. т.е. в матрице 3x3 просто записаны i,j,k новой системы.
Сообщение от andreysv
Поэтому использую простейшую матрицу поворота (для камеры в визуализаторе графов - самый лучший вариант).
Да в принципе LookAt матрица тоже штука простая. а трансформация относительно локальных осей вообще применяется везде и повсюду. в любой компьютерной игре объекты обычно вокруг своих осей вертятся а не вокруг глобальных. Так же собственно говоря как и в реальном мире.
Вопрос: Локальная функция *.срр файла

Есть несколько срр файлов.
и я хочу в них определить локальные функции с одинаковым именем и параметрами.
они нигде больше не обьявлены кроме этих срр файлов.
то-есть компилятор без проблем может скомпилировать каждый срр файл в обьектный.
Проблемы начинаются у линковщика, который видит несколько одинаковых функций в разных обьектных файлах.
Можно ли обьявить функцию локальной для файла? Чтоб линковщик при компоновке её не трогал.
Ответ: можно использовать анонимное пространство имен
C++
1
2
3
4
namespace
{
    // тут твоя ф-ция
}
либо использовать ключевое слово static
C++
1
2
3
4
static void f()
{
    // ...
}
первый С++'ный подход, второй чисто сишный.
Вопрос: Пространства имён с++

Может я отсталый совсем, но перечислите пожалуйста все известные вам пространства имён в с++
Ответ: Sasha1239, пространство имен можно задать самому, следовательно, пространств имен может быть сколь угодно много (ну, не до бесконечности, конечно, конечный предел все равно имеется).
Определяется пространство имен следующим образом:
C++
1
2
3
4
namespace testNamespace // задали имя пространству имен
{
  // пишем тут что-нибудь
}
Насколько мне известно, также пространства имен можно доопределять,
а еще можно создавать безымянные пространства имен (вернее, визуально они будут безымянными)
C++
1
2
3
4
namespace
{
  // пишем тут что-нибудь
}
А так, помимо этого есть глобальное ( :: ) пространство и пространство имен std::
Вопрос: Сжатие на основе сравнения

Сжатие на основе сравнения. вводится m различных сообщений произвольной длины, последовательности начальных символов могут совпадать. Если такое совпадение имеется в двух сообщениях, следующих друг за другом, то начальные символы второго сообщения заменяются программой на эквивалентное представление вида *(k), где k - количество совпадающих символов. Пример:
александров
алексеева
алехин

александров
*(5)еева
*(3)хин

Помогите реализовать, пожалуйста.
Ответ:

Не по теме:

Делал такое для сжатия Wordlist'ов. Не на Pascal, разумеется.


Цитата Сообщение от Berserk707 Посмотреть сообщение
александров
*(5)еева
*(3)хин
Код Code
1
2
3
александров
'еева
%хин
Вопрос: Как определить переменную вне пространстве имён?

Нужно объявить переменную входящую в пространство имён p3, при этом вне функции.

C++
1
2
3
4
5
namespace p3
{
    int b;//Пахает
}
int p3::a; //Не пахает(
Ответ:
Сообщение от Aqua77
Нужно объявить переменную входящую в пространство имён p3, при этом вне функции.
Вне какой еще "функции" и при чем здесь вообще какая-то "функция"?

Квалифицированные имена (то есть имена с '::') могут ссылаться только на уже определенные ранее сущности. Невозможно определить новую сущность используя квалифицированное имя.

И нет, невозможно добавить сущность в пространство имен снаружи этого пространства имен. Способ всегда только один: открываем пространство имен, добавляем все что надо (используя неквалифицированные имена, разумеется), закрываем пространство имен.

Сообщение от Aqua77
А в книге этой написана белиберда полнейшая.
Вопрос: Имя типа или пространства имен "Tasks" отсутствует в пространстве имен "System.Threading"

Всем привет! В Microsoft Visual C# 2008 Express Edition вылетает ошибка :
Имя типа или пространства имен "Tasks" отсутствует в пространстве имен "System.Threading" (пропущена ссылка на сборку?)
Подскажите что делать, в сборке нет ссылки, где-то скачать её может ?
Ответ: Максим2014, пространство имен System.Threading.Tasks было добавлено в .NET 4.0. VS 2008 поддерживает максимум .NET 3.5. Нужно переходить хотя бы на VS 2010.
Вопрос: Поиск в пространстве состояний (поиск по графам тоже сюда!)

Поскольку данные темы очень часто появляются на форуме, то тут будут подробно рассмотрены стандартные виды поиска. Многое взято из книги Сошникова "Парадигма логического программирования", куда очень советую заглянуть. Буду выкладывать коды на SWI прологе и Visual Prolog 5.2/Turbo Prolog.

Поиск в глубину.
Данный поиск просто ищет любой путь между двумя состояниями, поэтому нет никаких гарантий, что он окажется кратчайшим. Можно использовать для нахождения всех путей между двумя состояниями. Применяется для не взвешенных графов.
Итак, допустим у нас есть неориентированный граф
Поиск в пространстве состояний (поиск по графам тоже сюда!)
И мы хотим найти все пути от вершины а до вершины с.
Для начала надо задать правило одного шага move
Код Prolog
1
2
3
4
5
6
7
8
m(a,b).
m(b,c).
m(a,d).
m(b,d).
m(c,d).
m(c,e).
m(d,e).
move(A,B):-m(A,B);m(B,A). %поскольку граф неориентированный
Пройденный путь будет храниться в виде списка состояний, но в обратном порядке, т.е стартовая вершина будет расположена в конце, а текущая вершина в начале.
Чтобы продлить путь на один ход, то надо найти какой шаг мы можем сделать, и во избежание зацикливания проверить, чтобы этот шаг не привел к состоянию, в котором мы уже побывали.
Код Prolog
1
2
prolong([Temp|Tail],[New,Temp|Tail]):-
    move(Temp,New),not(member(New,[Temp|Tail])).
Теперь сам предикат поиска в глубину
Код Prolog
1
2
3
4
5
6
dpth([Finish|Tail],Finish,[Finish|Tail]). %если текущая вершина
%совпадает с конечной, то путь найден
dpth(TempWay,Finish,Way):-
    prolong(TempWay,NewWay), %пробуем сделать шаг 
    dpth(NewWay,Finish,Way).%продолжаем поиск уже 
    %с учетом сделанного шага
Вспомогательный предикат для удобства пользователя
Код Prolog
1
2
3
4
search_dpth(Start,Finish):-
    dpth([Start],Finish,Way),%вызываем поиск в глубину,
    %считая, что пока путь состоит только из начальной вершины
    show_answer(Way).%выводим путь на экран в наглядном виде
Для вывода пути на экран используется специальный предикат, в котором учитывается, что путь храниться в обратном порядке
Код Prolog
1
2
3
show_answer([_]):-!.
show_answer([A,B|Tail]):-
    show_answer([B|Tail]),nl,write(B),write(' -> '),write(A).
И теперь результатом работы
?- search_dpth(a,c).

a -> b
b -> c
true
Нахождение всех путей
?- search_dpth(a,c),nl,nl,nl,fail.

a -> b
b -> c



a -> b
b -> d
d -> e
e -> c



a -> b
b -> d
d -> c



a -> d
d -> e
e -> c



a -> d
d -> b
b -> c



a -> d
d -> c


false.

Чтобы изменить под другую задачу, то в большинстве случаев достаточно будет просто поменять предикат move. Например у нас есть шарики:
Поиск в пространстве состояний (поиск по графам тоже сюда!)
Каждый из них может перемещаться только в соседнее пустой поле, или перепрыгивать в пустое поле через один шарик противоположного цвета. Надо поменять шарики местами.
Код Prolog
1
2
3
4
5
6
7
8
move(A,B):-
    append(Begin,[b,'_'|End],A),append(Begin,['_',b|End],B).
move(A,B):-
    append(Begin,['_',w|End],A),append(Begin,[w,'_'|End],B).
move(A,B):-
    append(Begin,[b,w,'_'|End],A),append(Begin,['_',w,b|End],B).
move(A,B):-
    append(Begin,['_',b,w|End],A),append(Begin,[w,b,'_'|End],B).
Результат работы программы
?- search_dpth([b,b,b,'_',w,w,w],[w,w,w,'_',b,b,b]).

[b, b, b, _, w, w, w] -> [b, b, _, b, w, w, w]
[b, b, _, b, w, w, w] -> [b, b, w, b, _, w, w]
[b, b, w, b, _, w, w] -> [b, b, w, b, w, _, w]
[b, b, w, b, w, _, w] -> [b, b, w, _, w, b, w]
[b, b, w, _, w, b, w] -> [b, _, w, b, w, b, w]
[b, _, w, b, w, b, w] -> [_, b, w, b, w, b, w]
[_, b, w, b, w, b, w] -> [w, b, _, b, w, b, w]
[w, b, _, b, w, b, w] -> [w, b, w, b, _, b, w]
[w, b, w, b, _, b, w] -> [w, b, w, b, w, b, _]
[w, b, w, b, w, b, _] -> [w, b, w, b, w, _, b]
[w, b, w, b, w, _, b] -> [w, b, w, _, w, b, b]
[w, b, w, _, w, b, b] -> [w, _, w, b, w, b, b]
[w, _, w, b, w, b, b] -> [w, w, _, b, w, b, b]
[w, w, _, b, w, b, b] -> [w, w, w, b, _, b, b]
[w, w, w, b, _, b, b] -> [w, w, w, _, b, b, b]
true

Код целиком для SWI Prolog
Код Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
%m(a,b).
%m(b,c).
%m(a,d).
%m(b,d).
%m(c,d).
%m(c,e).
%m(d,e).
 
%move(A,B):-m(A,B);m(B,A). %поскольку граф неориентирован
 
move(A,B):-
    append(Begin,[b,'_'|End],A),append(Begin,['_',b|End],B).
move(A,B):-
    append(Begin,['_',w|End],A),append(Begin,[w,'_'|End],B).
move(A,B):-
    append(Begin,[b,w,'_'|End],A),append(Begin,['_',w,b|End],B).
move(A,B):-
    append(Begin,['_',b,w|End],A),append(Begin,[w,b,'_'|End],B).
 
search_dpth(Start,Finish):-dpth([Start],Finish,Way),show_answer(Way).
 
prolong([Temp|Tail],[New,Temp|Tail]):-
    move(Temp,New),not(member(New,[Temp|Tail])).
 
dpth([Finish|Tail],Finish,[Finish|Tail]).
dpth(TempWay,Finish,Way):-
    prolong(TempWay,NewWay),dpth(NewWay,Finish,Way).
 
show_answer([_]):-!.
show_answer([A,B|Tail]):-
    show_answer([B|Tail]),nl,write(B),write(' -> '),write(A).

Код целиком для Визуал Пролог 5.2/Турбо Пролог для графа
Код Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
domains
slist=string*
 
predicates
m(string,string).
move(string,string).
search_dpth(string,string).
prolong(slist,slist).
dpth(slist,string,slist).
show_answer(slist).
member(string,slist).
 
clauses
m(a,b).
m(b,c).
m(a,d).
m(b,d).
m(c,d).
m(c,e).
m(d,e).
 
move(A,B):-m(A,B);m(B,A).
 
search_dpth(Start,Finish):-dpth([Start],Finish,Way),show_answer(Way).
 
member(H,[H|_]).
member(H,[_|Tail]):-member(H,Tail).
 
prolong([Temp|Tail],[New,Temp|Tail]):-
    move(Temp,New),not(member(New,[Temp|Tail])).
 
dpth([Finish|Tail],Finish,[Finish|Tail]).
dpth(TempWay,Finish,Way):-
    prolong(TempWay,NewWay),dpth(NewWay,Finish,Way).
 
show_answer([_]):-!.
show_answer([A,B|Tail]):-
    show_answer([B|Tail]),nl,write(B," -> ",A).
goal
search_dpth(a,c),nl,nl,nl,fail.

Код целиком для Визуал Пролог 5.2/Турбо Пролог для шариков
Код Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
domains
slist=string*
slistlist=slist*
 
predicates
move(slist,slist).
search_dpth(slist,slist).
prolong(slistlist,slistlist).
dpth(slistlist,slist,slistlist).
show_answer(slistlist).
member(slist,slistlist).
append(slist,slist,slist).
 
clauses
move(A,B):-
    append(Begin,[b,"_"|End],A),append(Begin,["_",b|End],B).
move(A,B):-
    append(Begin,["_",w|End],A),append(Begin,[w,"_"|End],B).
move(A,B):-
    append(Begin,[b,w,"_"|End],A),append(Begin,["_",w,b|End],B).
move(A,B):-
    append(Begin,["_",b,w|End],A),append(Begin,[w,b,"_"|End],B).
 
search_dpth(Start,Finish):-dpth([Start],Finish,Way),show_answer(Way).
 
member(H,[H|_]).
member(H,[_|Tail]):-member(H,Tail).
 
append([],B,B).
append([H|Tail],B,[H|NewTail]):-append(Tail,B,NewTail).
 
prolong([Temp|Tail],[New,Temp|Tail]):-
    move(Temp,New),not(member(New,[Temp|Tail])).
 
dpth([Finish|Tail],Finish,[Finish|Tail]).
dpth(TempWay,Finish,Way):-
    prolong(TempWay,NewWay),dpth(NewWay,Finish,Way).
 
show_answer([_]):-!.
show_answer([A,B|Tail]):-
    show_answer([B|Tail]),nl,write(B," -> ",A).
goal
search_dpth([b,b,b,"_",w,w,w],[w,w,w,"_",b,b,b]).
Ответ: Жадный алгоритм поиска

При поиске пути можно как-то учитывать насколько близко от финишного состояния(в смысле какого-то критерия) находиться текущее состояние. Этот критерий называется эвристической функцией или просто эвристикой. Он ставит в соответствие двум состоянием определенное число, которое характеризует "расстояние" между ними. Например для известной задачи о передвижении мебели эвристикой может быть количество предметов, которые на данном этапе стоят не на желаемых местах, а для точек на плоскости просто геометрическое расстояние между ними.
В данном алгоритме поиска приоритет пути определяется не его суммарной длиной (она вообще не подсчитывается), а близостью конечной вершиной пути и заданной финишной вершиной.
Допустим у нас есть набор точек на плоскости, некоторые из которых соединены между собой
Поиск в пространстве состояний (поиск по графам тоже сюда!)
Эвристикой будем выступать геометрическое расстояние между ними.
Данную структуру можно задать как набор точек с их координатами, и набор связывающих их линий
Код Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
point(a,2,5).
point(b,4,5).
point(c,0,0).
point(d,4,10).
point(e,7,8).
point(f,12,7).
point(g,14,4).
 
r(a,c).
r(c,b).
r(b,g).
r(g,f).
r(g,d).
r(f,d).
r(e,d).
r(a,e).
 
road(A,B):-r(A,B);r(B,A).
Путь у нас опять же будет представлен списком вершин, немного изменить функция одного шага
Код Prolog
1
prolong([Temp|Tail],[New,Temp|Tail]):-road(Temp,New),not(member(New,[Temp|Tail])).
И введем эвристическую функцию, в которой нам важны текущая и конечная вершины пути
Код Prolog
1
2
wt([TempPoint|_],FinishPoint,L):-point(TempPoint,XA,YA),point(FinishPoint,XB,YB),
    Sum is (XA-XB)*(XA-XB)+(YA-YB)*(YA-YB), L is sqrt(Sum).
Предикат вставки нового пути на положенное место в списке путей также измениться
Код Prolog
1
2
3
4
%теперь сравниваются эвристики конечных вершин пути
placeone(Way,[WayH|Tail],Finish,[Way,WayH|Tail]):-wt(Way,Finish,A),wt(WayH,Finish,B),A=<B,!.
placeone(Way,[WayH|Tail],Finish,[WayH|NewTail]):-placeone(Way,Tail,Finish,NewTail).
placeone(Way,[],_,[Way]).
В остальном поиск не отличается от поиска на основе весовой функции.
Результат работы программы:
?- search_grd(g,a).

g -> b
b -> c
c -> a
true .

Но этот результат не правилен, правильным ответом является
?- search_bst(g,a).

g -> d
d -> e
e -> a
Length of way: 21.0984
true

Т.е как мы видим, данный алгоритм не гарантирует правильности результатов. Программа получила такой ответ потому что из путей в одну дорогу наиболее приоритетным является путь g-b, т.к b ближе к финишной вершине, чем f или d. Путь g-b можно продлить только единственным способом g-b-c, и вершина c опять же оказывается не менее приоритетной, чем f или d, после чего мы просто завершаем путь. И вот получилось, что b близка к финишной, c не далеко от финишной, а то, что они друг от друга далеки, совсем не учитывалось, что и привело к ошибке.
Но на практике такой алгоритм часто можно использовать, ведь, например, если бы выполнялся поиск пути между двумя реальными городами, то результат был бы скорее всего верным, из-за равномерного распределения городков/поселков/деревень и соответствующих дорог между ними.
Сравнение порядка путей, полученных разными алгоритмами
Результат жадного алгоритма
?- search_grd(g,a),nl,nl,nl,fail.

g -> b
b -> c
c -> a



g -> d
d -> e
e -> a



g -> f
f -> d
d -> e
e -> a

Результат поиска на основе весовой функции
?- search_bst(g,a),nl,nl,nl,fail.

g -> d
d -> e
e -> a
Length of way: 21.0984



g -> f
f -> d
d -> e
e -> a
Length of way: 21.5861



g -> b
b -> c
c -> a
Length of way: 21.8382

Код целиком для SWI Prolog
Код Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
point(a,2,5).
point(b,4,5).
point(c,0,0).
point(d,4,10).
point(e,7,8).
point(f,12,7).
point(g,14,4).
 
r(a,c).
r(c,b).
r(b,g).
r(g,f).
r(g,d).
r(f,d).
r(e,d).
r(a,e).
 
road(A,B):-r(A,B);r(B,A).
 
prolong([Temp|Tail],[New,Temp|Tail]):-road(Temp,New),not(member(New,[Temp|Tail])).
 
wt([TempPoint|_],FinishPoint,L):-point(TempPoint,XA,YA),point(FinishPoint,XB,YB),
    Sum is (XA-XB)*(XA-XB)+(YA-YB)*(YA-YB), L is sqrt(Sum).
 
place([],SortedWays,_,SortedWays).
place([Way|Tail],PrevWays,Finish,SortedWays):-
    placeone(Way,PrevWays,Finish,PrevWays1),place(Tail,PrevWays1,Finish,SortedWays).
 
placeone(Way,[WayH|Tail],Finish,[Way,WayH|Tail]):-wt(Way,Finish,A),wt(WayH,Finish,B),A=<B,!.
placeone(Way,[WayH|Tail],Finish,[WayH|NewTail]):-placeone(Way,Tail,Finish,NewTail).
placeone(Way,[],_,[Way]).
 
search_grd(Start,Finish):-
    grd([[Start]],Finish,Way),show_answer(Way).
 
grd([[Finish|Tail]|_],Finish,[Finish|Tail]).
grd([TempWay|OtherWays],Finish,Way):-
    findall(W,prolong(TempWay,W),Ways),
    place(Ways,OtherWays,Finish,NewWays),grd(NewWays,Finish,Way).
 
show_answer([_]):-!.
show_answer([A,B|Tail]):-
    show_answer([B|Tail]),nl,write(B),write(' -> '),write(A).

Код целиком для Визуал Пролог 5.2/Турбо Пролог
Код Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
domains
way=string*
ways=way*
 
predicates
point(string,real,real).
r(string,string).
road(string,string).
prolong(way,way).
wt(way,string,real).
place(ways,ways,string,ways).
placeone(way,ways,string,ways).
search_grd(string,string).
grd(ways,string,way).
show_answer(way).
member(string,way).
 
clauses
point(a,2,5).
point(b,4,5).
point(c,0,0).
point(d,4,10).
point(e,7,8).
point(f,12,7).
point(g,14,4).
 
r(a,c).
r(c,b).
r(b,g).
r(g,f).
r(g,d).
r(f,d).
r(e,d).
r(a,e).
 
road(A,B):-r(A,B);r(B,A).
 
prolong([Temp|Tail],[New,Temp|Tail]):-road(Temp,New),not(member(New,[Temp|Tail])).
 
member(H,[H|_]).
member(H,[_|Tail]):-member(H,Tail).
 
wt([TempPoint|_],FinishPoint,L):-point(TempPoint,XA,YA),point(FinishPoint,XB,YB),
    Sum = (XA-XB)*(XA-XB)+(YA-YB)*(YA-YB), L = sqrt(Sum).
 
place([],SortedWays,_,SortedWays).
place([Way|Tail],PrevWays,Finish,SortedWays):-
    placeone(Way,PrevWays,Finish,PrevWays1),place(Tail,PrevWays1,Finish,SortedWays).
 
placeone(Way,[WayH|Tail],Finish,[Way,WayH|Tail]):-wt(Way,Finish,A),wt(WayH,Finish,B),A<=B,!.
placeone(Way,[WayH|Tail],Finish,[WayH|NewTail]):-placeone(Way,Tail,Finish,NewTail).
placeone(Way,[],_,[Way]).
 
search_grd(Start,Finish):-
    grd([[Start]],Finish,Way),show_answer(Way).
 
grd([[Finish|Tail]|_],Finish,[Finish|Tail]).
grd([TempWay|OtherWays],Finish,Way):-
    findall(W,prolong(TempWay,W),Ways),
    place(Ways,OtherWays,Finish,NewWays),grd(NewWays,Finish,Way).
 
show_answer([_]):-!.
show_answer([A,B|Tail]):-
    show_answer([B|Tail]),nl,write(B),write(" -> "),write(A).
 
goal
search_grd(g,a),nl,nl,nl,fail.
Вопрос: Поиск в пространстве состояний

Поиск пространств и состояний (в глубину, в ширину,евристический поиск)
Поиск в пространстве состояний (в глубину, в ширину, эвристический).
Ответ: Хоть бы переписали правильно.. На самом деле "Поиск в пространстве соостояний"

Читали?