ზოგიერთი რიცხვითი ექსპერიმენტი სიმეტრიულ თამაშებზე

ავტორი: კობა გელაშვილი
საკვანძო სიტყვები: სიმეტრიული თამაში, წრფივი პროგრამირება
ანოტაცია:

არსებობის 80 წლის მანძილზე წრფივი პროგრამირება (LP) იქცა მძლავრ იარაღად თეორიულ კომპიუტერულ მეცნიერებასა და ალგორითმების აგებაში. ამჟამად, LP ეფექტურად ხსნის მთელრიცხვა პროგრამირების, გრაფთა თეორიის და სხვა ამოცანებს და ფართოდ გამოიყენება რთული ამოცანების მიახლოებითი ალგორითმების ასაგებად. ამას გარდა, მრავალი გამოთვლითი ამოცანისთვის, ეფექტური ალგორითმების დამტკიცებები ეფუძნება LP-ს. წრფივ პროგრამირებას აქვს რამდენიმე ეკვივალენტური ჩამოყალიბება. ჩვენ ექსპერიმენტებს ვატარებთ სიმეტრიულ თამაშებზე. ამ შემთხვევაში, შესაძლებელია საჯარიმო ფუნქციების გამოყენება ვრცელი სპექტრის მქონე უპირობო მინიმიზაციის ამომხსნელ პროგრამებთან ერთად. მაგალითად, როგორიცაა l-bfgs (იხ.[1]) ან მოდიფიცირებული მძიმე ბრითვი (იხ. [2]). შედეგად ვიღებთ ალგორითმს, რომელიც კონკურენტუნარიანია ღია კოდის მქონე და კომერციულ ამომხნელ პროგრამებთან. ამ მიდგომაში მთავარი სირთულე არის შეზღუდვა ცვლადის ნიშანზე და ჩვენ ორ ეტაპად ვხსნით ამ ამოცანას. უხეშად, მაგრამ გარკვული დაწვრილმანებით განვიხილოთ ეს საკითხი.

მიმაგრებული ფაილები:

ზოგიერთი რიცხვითი ექსპერიმენტი სიმეტრიულ თამაშებზე [ka]
On some numerical experiments on symmetric games [en]