Дәріс 6. Тарату, шектеу және таңдау әдістері.

Есептерді толық теріп шығу әдісімен шешу. Кез келген комбинаторлық есептің мәнін келесі түрде жүйелеуге болады:

«Сөйлемдегі, Х-ті табу кеңістігіне әр түрлі нүктенің кейбір соңғы саны енеді, көптеген Х элементінен К(х) қанағаттанған жиынтықтан х шартын табу».

Осындай жағдайлар дискреттік табиғи элементтерімен жұмыс істегенде үнемі туындайды; логикалық басқатырғыш; қоймадағы қорды толтыру жағдайы; көптеген мүмкіндіктерден шешім таңдау; жаңа зауытты орналастыру жерін анықтау; баған бойынша жүру жолы; теореманы дәлелдеу. Барлық осы жағдайда Х-ті табу кеңістігі соңғы және дискреттік болып табылады. Соңғысы, барлық Х нүктесі бір-бірінен бөлінгенін білдіреді. Дәл осындай есептерді шешу кезінде таңдау әдісі қолданылады.

Толық таңдау әдісі. Кейбір соңғы көптеген тиісті элементті табу талап етілгенде, керекті элемент табылғанша, барлық элементті іріктеуімізге болады. Егер көптеген қуат қолмен санағанда 10³ немесе машинамен санағанда 10^е аспаса, бұл әдіс қолайлы, қарапайым және жақсы жұмыс істеуге мүмкіндік береді.

Қозғалыс сызбасы келесі түрде:

1. Көптеген Х мәнінен әлі қарастырмаған бірінші Х_Q элементін таңдау;

2. К_(ХО) жиынтық шартын тексеру;

3.   Егер қандай да бір шарт орындалмаса, «қайтадан бастау»;

4. Егер барлық шарт орындалса, Х_О шешімі болып табылады.

Есептерді градиенттік әдіспен шешу. Градиенттік әдіснақты есептерді шығаруда жиі қолданылады: мұның мәні – жоғары дәрежеге тез жету үшін ең қиын жолмен жылжу керек. Егер біз автокөлікпен қалада солтүстіктен оңтүстікке қарай жүргіміз келсе, біз осы бағытты көп уақытқа сақтауға тырысамыз, ал егер де қозғалыс шарты бізді одан аластатса, біз бұл ауытқушылықты мүмкіндігінше аз мөлшерде орындауға тырысамыз. «Тауға көтерілу» немесе градиенттік стратегия кезекті локальді оптимумдар арқылы негізгі оптимумға қол жеткізуден тұрады (сурет 18). Бұл тәжірибенің нәтижесінде іздеу кеңістігі сыртқа қарай шығыңқы болмағанда, ол аз әсер берсе де, стратегия толығымен қолайлы.

сурет 18.

Кеңістік күйде іздеу стратегиясы және құрылымы. Іздеу алгоритмін әзірлеп, енгізу үшін, әзірлеуші талдай алуы және олардың қозғалысын жобалай алуы керек. Олардың алдында мынадай сұрақтар тұрады:

Іздеу үрдісінде шешімді табу кепілі бар ма?

Іздеуде соңына жетуге бола ма, әлде онда бар нәтижеге жету мүмкін емес пе?

Егер шешімі табылса, ол оңайлы ма?

Кеңістік күйдегі іздеу теориясы осы сұрақтарға жауап береді.

Кеңістік күйдегі баған ретінде есепті елестетіп, есепті шығару барысында және оның қиындығы мен құрылымын талдау үшін баған теориясын қолдануға болады. Бағанның биіктігі – шешім үрдісінің дискреттік күйі, доға – олардың ортасынан іздеу.

Эвристикалық іздеу. Эвристика – «жаңалық ашу, ойлап табу ережесін және әдістерін меңгеру». Кеңістік күйдегі іздеу эвристикасы сол кеңістіктен жағдайдың мүмкіндігінше тиімді шешімін табуға әкелетін жолды таңдау ережесінің жиынтығы түрінде анықталады.

Мамандар жасанды парасаты бойынша эвристиканы 2 жағдайда қолданыды.

1. Шығыс берілімі мен есептің қойылуының белгісіздігіне байланысты жағдайдың нақ бір шешімі болмауы мүмкін. Медициналық диагноз қою – осындай мәселеге мысал. Белгілі бір белгінің жиынтығында бірнеше себеп болуы мүмкін; сондықтан дәрігерлер нақты бір диагноз қойып және соған орай емдеу әдісін таңдау үшін эвристикалық әдісті қолданады.

2.  Мәселенің нақты шешімі болуы мүмкін, бірақ оны іздеу өте жоғары (өте қиын) болуы мүмкін. Көптеген есептерде (мысалы шахмат ойыны) кеңістікті мүмкіндік жағдайдың өсуі экспоненциалды өседі. Эвристика неғұрлым перспективті жолмен іздеу жүргізуге мүмкіндік береді.

Крестик – нолик пен нөлдер ойынын қарастырсақ, бұл ойында толық іздеу қиынырақ, бірақ мүмкін. Алғашқы 9 жүрістің әрқайсысына 8 мүмкін жауап болады. Өз кезегіне, түрлі 7 нұсқамен жауап беруге болады. Қарапайым талдау ортақ 9 мүмкіндік жағдайды табуға жол ашады.

Есептің симметриясын есепке ала отыра, іздеу кеңістігін азайтуға (кемітуге) болады. Көптеген мүмкін кескіндерді іздеу мәселесі ойын тақтаның мүмкін симметриялы пішінді іздеуге жинақталады. -> 9 емес 3 қана мүмкін бірінші жүріс бар – бұрышқа, жоғары орталық торға және торкөздің ортасына. Қарапайым эвристика іздеудің керегі жоққа әкелуі мүмкін – мұндай жүрістерді жеңіс сызығында крестиктердің саны көбірек тоқталарда жүруге болады. «Крестик - нолик» ойынының бірінші 3 күйі осылайша жаңылысқан, егер әлеуетті жеңген саны тең болса, онда осылардың ішінен бірінші күйді аламыз. Кейін алгоритм ең жоғарғы эвристикалық мәнін таңдайды. Х жүру үшін орталық торды таңдаймыз. Мұндағы мүмкін болған жүрістер ғана емес, кейін жүретін жүрістер де жойылып қалады. Бұдан бірінші жүрістен кейін кеңістік мөлшері 2/3 дейін кішірейеді. Оппонент бірінші жүрістен кейін екінші жүрістің біреуін ғана таңдай алады. Оппонент қайсысын таңдағанымен, ойынның соңында эвристика қолданылуы мүмкін. Эвристика «жоғары жеңіл сызығының санын» мүмкін болатын жүрістердің ішінен таңдап алынады.  

Дәріс 7. Ойындар және ойын бағдарламалары.