Искусственный интеллект как эмпирическая проблема
и часто цитируемым примером связи
Выразительным и часто цитируемым примером связи между поиском и представлением, а также трудности выбора удобного представления является задача размещения костей домино на усеченной шахматной доске. Допустим, имеется шахматная доска и набор костей домино, причем каждая закрывает ровно две клетки на доске. Положим также, что у доски не хватает нескольких клеток - на рис. 16.1 отсутствуют верхний левый и нижний правый уголки.
Рис. 16.1. Усеченная шахматная доска с двумя клетками, закрытыми костью домино
Задача состоит в том, чтобы установить, можно ли разместить кости домино на доске так, чтобы все поля были закрыты, и при этом каждая кость покрывала две и только две клетки. Можно попытаться решить проблему, перебрав все варианты расположения костей. Это типичный пример решения на основе поиска, который является естественным следствием представления доски в виде простой матрицы, игнорирующим такие, казалось бы, незначительные особенности, как цвет поля. Сложность подобного поиска просто невероятна. Для эффективного решения необходимо применение эвристических методов. Например, можно отсечь частные решения, которые оставляют изолированными отдельные клетки. Можно также начать с решения задачи для досок меньшего размера, таких как 2x2, 3x3, и постараться расширить решение до ситуации 8x8.
Опираясь на более сложное представление, можно получить изящное решение. Для этого нужно учесть тот факт, что каждая кость должна одновременно покрывать белую и черную клетки. На усеченной доске 32 черные клетки, но лишь 30 белых, следовательно, требуемое размещение невозможно. Таким образом, в системах, основанных на символьных рассуждениях, возникает серьезный вопрос: существуют ли представления, позволяющие оперировать знаниями с такой степенью гибкости и творческого подхода? Как может конкретное представление изменять свою структуру по мере появления новых сведений о предметной области?
Эвристика - это третий важный компонент символьного ИИ после представления и поиска. Эвристика - это механизм организации поиска среди альтернатив, предлагаемых конкретным представлением. Эвристики разрабатываются для преодоления сложности полного перебора, являющейся непреодолимым барьером на пути получения полезных решений многих классов интересных задач. В компьютерной среде, как и в человеческом обществе, интеллект нуждается в обоснованном решении "что делать дальше". На протяжении истории развития ИИ эвристики принимали множество форм.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий