Популярно об ИИ
Возможно, разделение на людей и роботов не столь существенно. Важнее, обладает объект разумом или нет.
Айзек Азимов «Стальные пещеры»
Что самое интересное, люди стремятся мыслить как роботы, в то же время искусственному интеллекту прививается «очеловечивание» мышления. Можно сказать, что существует некое противоборство между математическим шахматно-переборным и образно-ассоциативным принципами. Например, машина не может нарисовать толковой картины, написать музыку, хотя такие попытки нет-нет да и появляются, хотя у машины нет такого понятия, присущего человеку, как вкус. Что касается нашего стремления мыслить как роботы, то тут примеров можно привести очень много. Например, современная архитектура в большинстве случаев подразумевает правильные геометрические формы. И что уж говорить о чемпионатах по компьютерным играм. Некогда я с большим удовольствием наблюдал за игроками в Starcraft, которые с математической точностью знали несколько вариантов стратегий развития, использовали «шаблонные» тактики и так далее.
Сегодня мы дадим вам некоторые задачи на самостоятельную проработку, а также обсудим сопутствующие вопросы.
Задача коммивояжера (исправляем ошибку в рисунке)
Не так давно мне в руки попала книга В. Н. Касаткина «Необычные задачи математики» (Киев, «Родяньска школа», 1987). Там достаточно интересно и в популярной форме изложены ключевые принципы алгебраической логики и теории графов. Конечно, в таких книгах всегда интересны задачи. Причем именно «задача коммивояжера» является одной из известнейших. В книге приводится одна ее простейшая разновидность. Но… посмотрите внимательно на рисунок, полностью повторяющий тот, который был в книге.
Само условие звучит так: «Коммивояжер из пункта А отправляется в поездку и намерен, посетив по одному разу пункты B, С и D, вернуться в А. Схема расположения пунктов задана неориентированным графом. Утверждается, что ему безразлично, в каком порядке объезжать эти пункты. Так ли это? Почему?». Дело в том, что автор хотел показать одну хитрость, а именно, продемонстрировать ситуацию, когда расстояния при всех вариантах обходов равны одному и тому же числу.
А теперь, без всяких сложных алгоритмов по расчету графов, вручную вычислим маршруты. Напомню, что ошибка в книге была только на рисунке, а в ответах все правильно, потому как одно из чисел (расстояние) другое:
ABCDA, то же, что и ADCBA — 28+34+32+20 = 114.
ACDBA, то же, что и ABDCA — 36+32+24+28 = 120.
ACBDA, то же, что и ADBCA — 36+34+24+20 = 114.
Ответ не привожу, потому как ставлю перед вами иную задачу, вернее, сразу несколько:
. Найдите неправильное число, замените его на правильное.
. Напишите программный алгоритм для создания подобных данной «задач коммивояжера», который бы при наличии одного известного расстояния (например, AB) находил и расставлял значения других с учетом структуры приведенного графа. То есть, чтобы любой из вариантов обхода подразумевал одно и то же расстояние.
. Напишите программный алгоритм для создания подобных данной «задач коммивояжера», который бы при наличии двух известных расстояний (например, AB и AC, при условии, что AC>АВ) находил и расставлял значения других с учетом структуры приведенного графа. То есть, чтобы любой из вариантов обхода подразумевал одно и то же расстояние.
Найдите ошибку в графе согласно требованиям задачи
Другая задача из этой же книги
Это стандартная «задача четырех коней», в которой нужно найти минимальное количество ходов, за которые белые и черные фигуры поменяются местами. Для тех, кто ее еще не решал, рекомендуется «поломать» голову, а лучше создать дерево поиска (нарисовать). На этом же рисунке во втором варианте мы усложнили задание, использовав шесть фигур. Нужно найти наиболее емкое решение.
Задача «четырех коней» (1), задача «шести коней» (2)
Реальная задача
Как многим известно, ваш покорный слуга время от времени занимается профессиональными расчетами трансляционных акустических систем. Этому способствует собственноручно написанная программа Klariona-Shop, которая рассчитывает равномерность звукового покрытия, то есть, чтобы не было явно ощутимых перепадов в громкости и т.п. Кстати, Klariona-Shop — это специальная разновидность из семейства Klariona, в материалах по ИИ я описывал ее другие варианты, а именно, просто Klariona — распознавание образов, а также некоторые модули из Klariona-Chess, когда мы обсуждали шахматные алгоритмы.
Помимо равномерности звукового покрытия отдельные расчеты ведутся по прокладке кабелей.
Что вам предлагается сделать? Это реальный проект — магазин, находится в Минске:). Схема загрузилась в Klariona-Shop, соответственно, громкоговорители, их расположение и мощность уже посчитаны. Модели усилителя и колонок подобраны. Причем предполагается четыре отдельных независимых зоны, для каждой из которых есть отдельный регулятор громкости (в трансляционных системах он называется аттенюатором). Хотя, если честно, ваш покорный слуга практически никогда не использует варианты с аттенюаторами, поскольку программа хорошо считает равномерность, и дополнительных регуляторов обычно не требуется.
Реальное задание — трансляционная система для магазина
Ваша задача написать программный модуль (или прикинуть, как он будет работать), рассчитывающий оптимальную прокладку кабелей для каждой из зон, предусматривается последовательное подключение (провода соединяются на клеммах колонок). Для упрощения задачи — расстояние между колоннами, на которые подвешиваются колонки, везде одинаково и составляет 6 м. Места расположения громкоговорителей отмечены кружочками. Причем рекомендуется прокладка вдоль колонн и повороты под прямыми углами.
На самом деле, представленное задание достаточно простое, особенно для опытного человека, который может сразу на глаз прикинуть, что, где и как. Но, между тем, программный модуль, который автоматически все считает, иногда необходим. Например, нередко приходится вносить в схему всевозможные изменения по расстановке, количеству, перераспределению зон (нужно следить за суммарной мощностью каждой) и т.п.
А применяемые алгоритмы расчетов достаточно стандартны для ИИ, можно использовать различные варианты. Например, я просто сделал модуль по созданию деревьев, причем написал свой собственный, достаточно простой по структуре и реализации рекурсивный алгоритм.
Вы же можете использовать все, что вам известно в области работы с графами, деревьями и так далее.
htrue и hfalse
Теперь имеет смысл разъяснить один вопрос, который вызвал небольшие споры. Постараемся объяснить как можно проще — главное, не запутаться в трех столбах. Постоянные читатели наверняка помнят выпуск «Популярно об ИИ», в котором я рассказывал об одном усовершенствовании булевой логики, которое мне встретилось в экспериментальных моделях программирования. Напомню, что речь шла о добавлении двух промежуточных значений htrue (полуправда) и hfalse (полуложь). Градация такая (идем от «лжи» к «правде»): false (ложь), htrue (вероятно, правда, что это ложь), hfalse (вероятно ложь, что это правда), true (правда). Тогда я приводил пример со стаканом воды, заполненным наполовину, при этом true — заполнен, false — пустой. Оптимистическое утверждение, что он наполовину полон, не совсем соответствует истине, поскольку он наполняться не будет и полным никогда не станет, т.е. hfalse, а вот полупустой — это уже ближе к реалиям, т.е. htrue. Тогда мы еще говорили о том, что эти промежуточные значения описывают движение или стремление.
Чтобы четче понять саму структуру, приведем и другой вариант объяснения. Пример:
1. Иванов немного разбирается в сантехнике и хочет учиться.
2. Сидоров — плохой сантехник.
При этом обозначим, что true — это хороший сантехник, а false — «не сантехник». В данном случае первое утверждение — это hfalse (полуложь), потому как Иванов не является хорошим сантехником, но стремится (имеет желание) им стать, а второе — htrue (полуправда), поскольку Сидоров — все- таки сантехник, но при этом плохой специалист.
Как видите на данном примере, тяготения hfalse к true и htrue к false становятся очевидными. В результате получается градация: false — не сантехник, htrue — плохой сантехник, hfalse — потенциально хороший сантехник, true — хороший сантехник. Другими словами: hfalse — это потенциально true, htrue — точно не true, но и не false.
Модель достаточно сложна в понимании из-за своей перевернутости. Кстати, я приводил пример с полуоткрытой дверью лифта в определенный конкретный момент, то есть она или открывается, или закрывается. Не все тогда поняли это сравнение, например, один читатель написал: «Если дверь открывается, то значит, что она полуоткрыта». Тут немного другое. А именно, нельзя сказать, что она открыта, — hfalse (полуложь, т.е. более ложное утверждение), а так как войти невозможно, ее можно считать ближе к закрытой — htrue (полуправда, то есть это утверждение ближе к правде). Вот в чем вся соль. Понятие «полуправда» относится к истине ложного утверждения (ложное утверждение верно), «полуложь» — к правдивости истинного (истинное утверждение не достигнуто). По существу, дверь нельзя считать открытой, пока она не откроется.
Где это может использоваться в реале? На самом деле, спектр применения велик. Я, например, встречал задачи «по степени доверия», выявлению реального положения вещей по анализу утверждений. Например, вместо задания вы можете просто проанализировать выступление какого-нибудь политика, экономиста и т.п. В большинстве случаев вы ведь не можете сказать четко и определенно, говорит он правду или обманывает. Представьте, что он говорит: «В таком-то году мы достигнем такого-то оборота». При этом у нас есть два крайних положения: false — требуемый рост не состоится, true — нужный оборот достигнут.
Если к росту есть предпосылки, то утверждение можно воспринимать как hfalse (требуемого уровня оборота еще нет), если предпосылок не существует, как это ни странно прозвучит, — htrue, полуправда, но по отношению к тому, что утверждение false является верным.
Например, когда у Билла Клинтона в первый раз спросили о Монике Левински, он ответил, что никакой связи у него с ней не было. false — было, true — действительно не было. Поскольку тогда обыватели не были посвящены в тайны, но предпосылки подозревать все-таки существовали, данное заявление можно рассматривать как htrue по отношению к утверждению false:)).
Вообще, данное нововведение требует определенной доли абстрактного мышления, чтобы разобраться.
В принципе, hfalse и htrue выгодно применять в ситуациях не полной определенности, а определения тяготения к чему-либо. Помимо этого можно использовать для выявления потенциала коллективов, работников, апгрейда оборудования и так далее. Причем в программировании все намного легче, чем в объяснениях:).
Кристофер, christopher@tut.by
Айзек Азимов «Стальные пещеры»
Что самое интересное, люди стремятся мыслить как роботы, в то же время искусственному интеллекту прививается «очеловечивание» мышления. Можно сказать, что существует некое противоборство между математическим шахматно-переборным и образно-ассоциативным принципами. Например, машина не может нарисовать толковой картины, написать музыку, хотя такие попытки нет-нет да и появляются, хотя у машины нет такого понятия, присущего человеку, как вкус. Что касается нашего стремления мыслить как роботы, то тут примеров можно привести очень много. Например, современная архитектура в большинстве случаев подразумевает правильные геометрические формы. И что уж говорить о чемпионатах по компьютерным играм. Некогда я с большим удовольствием наблюдал за игроками в Starcraft, которые с математической точностью знали несколько вариантов стратегий развития, использовали «шаблонные» тактики и так далее.
Сегодня мы дадим вам некоторые задачи на самостоятельную проработку, а также обсудим сопутствующие вопросы.
Задача коммивояжера (исправляем ошибку в рисунке)
Не так давно мне в руки попала книга В. Н. Касаткина «Необычные задачи математики» (Киев, «Родяньска школа», 1987). Там достаточно интересно и в популярной форме изложены ключевые принципы алгебраической логики и теории графов. Конечно, в таких книгах всегда интересны задачи. Причем именно «задача коммивояжера» является одной из известнейших. В книге приводится одна ее простейшая разновидность. Но… посмотрите внимательно на рисунок, полностью повторяющий тот, который был в книге.
Само условие звучит так: «Коммивояжер из пункта А отправляется в поездку и намерен, посетив по одному разу пункты B, С и D, вернуться в А. Схема расположения пунктов задана неориентированным графом. Утверждается, что ему безразлично, в каком порядке объезжать эти пункты. Так ли это? Почему?». Дело в том, что автор хотел показать одну хитрость, а именно, продемонстрировать ситуацию, когда расстояния при всех вариантах обходов равны одному и тому же числу.
А теперь, без всяких сложных алгоритмов по расчету графов, вручную вычислим маршруты. Напомню, что ошибка в книге была только на рисунке, а в ответах все правильно, потому как одно из чисел (расстояние) другое:
ABCDA, то же, что и ADCBA — 28+34+32+20 = 114.
ACDBA, то же, что и ABDCA — 36+32+24+28 = 120.
ACBDA, то же, что и ADBCA — 36+34+24+20 = 114.
Ответ не привожу, потому как ставлю перед вами иную задачу, вернее, сразу несколько:
. Найдите неправильное число, замените его на правильное.
. Напишите программный алгоритм для создания подобных данной «задач коммивояжера», который бы при наличии одного известного расстояния (например, AB) находил и расставлял значения других с учетом структуры приведенного графа. То есть, чтобы любой из вариантов обхода подразумевал одно и то же расстояние.
. Напишите программный алгоритм для создания подобных данной «задач коммивояжера», который бы при наличии двух известных расстояний (например, AB и AC, при условии, что AC>АВ) находил и расставлял значения других с учетом структуры приведенного графа. То есть, чтобы любой из вариантов обхода подразумевал одно и то же расстояние.
Другая задача из этой же книги
Это стандартная «задача четырех коней», в которой нужно найти минимальное количество ходов, за которые белые и черные фигуры поменяются местами. Для тех, кто ее еще не решал, рекомендуется «поломать» голову, а лучше создать дерево поиска (нарисовать). На этом же рисунке во втором варианте мы усложнили задание, использовав шесть фигур. Нужно найти наиболее емкое решение.
Реальная задача
Как многим известно, ваш покорный слуга время от времени занимается профессиональными расчетами трансляционных акустических систем. Этому способствует собственноручно написанная программа Klariona-Shop, которая рассчитывает равномерность звукового покрытия, то есть, чтобы не было явно ощутимых перепадов в громкости и т.п. Кстати, Klariona-Shop — это специальная разновидность из семейства Klariona, в материалах по ИИ я описывал ее другие варианты, а именно, просто Klariona — распознавание образов, а также некоторые модули из Klariona-Chess, когда мы обсуждали шахматные алгоритмы.
Помимо равномерности звукового покрытия отдельные расчеты ведутся по прокладке кабелей.
Что вам предлагается сделать? Это реальный проект — магазин, находится в Минске:). Схема загрузилась в Klariona-Shop, соответственно, громкоговорители, их расположение и мощность уже посчитаны. Модели усилителя и колонок подобраны. Причем предполагается четыре отдельных независимых зоны, для каждой из которых есть отдельный регулятор громкости (в трансляционных системах он называется аттенюатором). Хотя, если честно, ваш покорный слуга практически никогда не использует варианты с аттенюаторами, поскольку программа хорошо считает равномерность, и дополнительных регуляторов обычно не требуется.
Ваша задача написать программный модуль (или прикинуть, как он будет работать), рассчитывающий оптимальную прокладку кабелей для каждой из зон, предусматривается последовательное подключение (провода соединяются на клеммах колонок). Для упрощения задачи — расстояние между колоннами, на которые подвешиваются колонки, везде одинаково и составляет 6 м. Места расположения громкоговорителей отмечены кружочками. Причем рекомендуется прокладка вдоль колонн и повороты под прямыми углами.
На самом деле, представленное задание достаточно простое, особенно для опытного человека, который может сразу на глаз прикинуть, что, где и как. Но, между тем, программный модуль, который автоматически все считает, иногда необходим. Например, нередко приходится вносить в схему всевозможные изменения по расстановке, количеству, перераспределению зон (нужно следить за суммарной мощностью каждой) и т.п.
А применяемые алгоритмы расчетов достаточно стандартны для ИИ, можно использовать различные варианты. Например, я просто сделал модуль по созданию деревьев, причем написал свой собственный, достаточно простой по структуре и реализации рекурсивный алгоритм.
Вы же можете использовать все, что вам известно в области работы с графами, деревьями и так далее.
htrue и hfalse
Теперь имеет смысл разъяснить один вопрос, который вызвал небольшие споры. Постараемся объяснить как можно проще — главное, не запутаться в трех столбах. Постоянные читатели наверняка помнят выпуск «Популярно об ИИ», в котором я рассказывал об одном усовершенствовании булевой логики, которое мне встретилось в экспериментальных моделях программирования. Напомню, что речь шла о добавлении двух промежуточных значений htrue (полуправда) и hfalse (полуложь). Градация такая (идем от «лжи» к «правде»): false (ложь), htrue (вероятно, правда, что это ложь), hfalse (вероятно ложь, что это правда), true (правда). Тогда я приводил пример со стаканом воды, заполненным наполовину, при этом true — заполнен, false — пустой. Оптимистическое утверждение, что он наполовину полон, не совсем соответствует истине, поскольку он наполняться не будет и полным никогда не станет, т.е. hfalse, а вот полупустой — это уже ближе к реалиям, т.е. htrue. Тогда мы еще говорили о том, что эти промежуточные значения описывают движение или стремление.
Чтобы четче понять саму структуру, приведем и другой вариант объяснения. Пример:
1. Иванов немного разбирается в сантехнике и хочет учиться.
2. Сидоров — плохой сантехник.
При этом обозначим, что true — это хороший сантехник, а false — «не сантехник». В данном случае первое утверждение — это hfalse (полуложь), потому как Иванов не является хорошим сантехником, но стремится (имеет желание) им стать, а второе — htrue (полуправда), поскольку Сидоров — все- таки сантехник, но при этом плохой специалист.
Как видите на данном примере, тяготения hfalse к true и htrue к false становятся очевидными. В результате получается градация: false — не сантехник, htrue — плохой сантехник, hfalse — потенциально хороший сантехник, true — хороший сантехник. Другими словами: hfalse — это потенциально true, htrue — точно не true, но и не false.
Модель достаточно сложна в понимании из-за своей перевернутости. Кстати, я приводил пример с полуоткрытой дверью лифта в определенный конкретный момент, то есть она или открывается, или закрывается. Не все тогда поняли это сравнение, например, один читатель написал: «Если дверь открывается, то значит, что она полуоткрыта». Тут немного другое. А именно, нельзя сказать, что она открыта, — hfalse (полуложь, т.е. более ложное утверждение), а так как войти невозможно, ее можно считать ближе к закрытой — htrue (полуправда, то есть это утверждение ближе к правде). Вот в чем вся соль. Понятие «полуправда» относится к истине ложного утверждения (ложное утверждение верно), «полуложь» — к правдивости истинного (истинное утверждение не достигнуто). По существу, дверь нельзя считать открытой, пока она не откроется.
Где это может использоваться в реале? На самом деле, спектр применения велик. Я, например, встречал задачи «по степени доверия», выявлению реального положения вещей по анализу утверждений. Например, вместо задания вы можете просто проанализировать выступление какого-нибудь политика, экономиста и т.п. В большинстве случаев вы ведь не можете сказать четко и определенно, говорит он правду или обманывает. Представьте, что он говорит: «В таком-то году мы достигнем такого-то оборота». При этом у нас есть два крайних положения: false — требуемый рост не состоится, true — нужный оборот достигнут.
Если к росту есть предпосылки, то утверждение можно воспринимать как hfalse (требуемого уровня оборота еще нет), если предпосылок не существует, как это ни странно прозвучит, — htrue, полуправда, но по отношению к тому, что утверждение false является верным.
Например, когда у Билла Клинтона в первый раз спросили о Монике Левински, он ответил, что никакой связи у него с ней не было. false — было, true — действительно не было. Поскольку тогда обыватели не были посвящены в тайны, но предпосылки подозревать все-таки существовали, данное заявление можно рассматривать как htrue по отношению к утверждению false:)).
Вообще, данное нововведение требует определенной доли абстрактного мышления, чтобы разобраться.
В принципе, hfalse и htrue выгодно применять в ситуациях не полной определенности, а определения тяготения к чему-либо. Помимо этого можно использовать для выявления потенциала коллективов, работников, апгрейда оборудования и так далее. Причем в программировании все намного легче, чем в объяснениях:).
Кристофер, christopher@tut.by
Компьютерная газета. Статья была опубликована в номере 18 за 2010 год в рубрике технологии
