lrsfourier - ออนไลน์ในคลาวด์

โครงการ:

ชื่อ

lrslib - แปลงระหว่างการตั้งค่าซ้ำของรูปทรงหลายเหลี่ยมนูน

เรื่องย่อ

ล input.ine

ล input.ine | lrsbuffer

lrsfourier ไฟล์.ine [ไฟล์ออก]

ซ้ำซ้อน input.ine

DESCRIPTION

รูปทรงหลายเหลี่ยมสามารถอธิบายได้โดยรายการความไม่เท่าเทียมกัน (ตัวแทน H) หรือตามรายการ
ของจุดยอดและรังสีสุดขั้ว (V-ตัวแทน). ล เป็นโปรแกรม C ที่แปลง a
การแสดงแทน H ของรูปทรงหลายเหลี่ยมเพื่อเป็นตัวแทน V และในทางกลับกัน ปัญหาเหล่านี้
เป็นที่รู้จักตามลำดับที่ จุดสุดยอด การแจงนับ และ กระจกนูน ลำเรือ ปัญหาที่เกิดขึ้น.

ฟุคุดะ คำถามที่พบบ่อย หน้า[1] มีการแนะนำปัญหาโดยละเอียดยิ่งขึ้นพร้อมกับ
เคล็ดลับที่เป็นประโยชน์มากมายสำหรับผู้ใช้ใหม่

lrsbuffer สามารถลบเอาต์พุตที่ซ้ำกันได้ ซ้ำซ้อน พบความไม่เท่าเทียมกันที่ซ้ำซ้อนใน
อินพุต

ไฟล์ รูปแบบ

รูปแบบไฟล์ได้รับการพัฒนาร่วมกับ Komei Fukuda และเข้ากันได้กับ CDD[2]

อินพุตสำหรับ ล เป็นตัวแทน H หรือ V- ของโพลิโทป

ชื่อ
{สายการเป็นตัวแทน}
{ตัวเลือก}
{เส้นตรง[3]}
เริ่ม
ล้านเหตุผล
{เมทริกซ์อินพุต}
ปลาย
{ตัวเลือก}

ชื่อ เป็นชื่อผู้ใช้ที่ให้มาสำหรับโพลิโทป ความคิดเห็นอาจปรากฏขึ้นก่อนการเริ่มต้นหรือ
หลังจบ และเพื่อหลีกเลี่ยงการตีความเป็นตัวเลือก ควรเริ่มต้นด้วยความพิเศษ
อักขระเช่น "*" หรือ "#"

ชื่อ เป็นชื่อผู้ใช้ที่ให้มาสำหรับโพลิโทป การแสดง เส้น เป็นทั้ง
"ตัวแทน H" หรือ "ตัวแทน V" หากละเว้น จะถือว่าแสดงแทน H NS
ค่าสัมประสิทธิ์อินพุตอ่านในรูปแบบอิสระและไม่ได้ตรวจสอบประเภท ค่าสัมประสิทธิ์คือ
คั่นด้วยช่องว่างสีขาว m คือจำนวนแถวและ n จำนวนคอลัมน์ของอินพุต
มดลูก

ตัวแทน H
จำนวนเต็ม m คือจำนวนของอสมการ และจำนวนเต็ม n คือมิติของ
อินพุต +1 รายการของความไม่เท่าเทียมกันมีค่าสัมประสิทธิ์ของความไม่เท่าเทียมกันของแบบฟอร์ม

a0 + a1x1+ ... + an-1 xn-1 >= 0

ความไม่เท่าเทียมกันนี้ถูกป้อนเป็นเส้น

ก0 ก1...อัน-1

สามารถป้อนค่าสัมประสิทธิ์เป็นจำนวนเต็มหรือตรรกยะในรูปแบบ x/y

ตัวแทน V
จำนวนเต็ม m คือจำนวนจุดยอดและรังสี และจำนวนเต็ม n คือมิติของ
อินพุต +1 แต่ละจุดยอดจะได้รับในรูปแบบ

1 ต่อ 0 ต่อ 1... ต่อ 1

แต่ละรังสีจะได้รับในรูปแบบ

0 r0 r 1... rn-1

โดยที่ r0 r 1... rn-1คือจุดบนรังสี

แต่ละไฟล์ต้องมีจุดยอดอย่างน้อยหนึ่งจุด สำหรับรูปทรงหลายเหลี่ยมที่มีขอบเขตจะไม่มี
รังสีเข้ามา สามารถป้อนค่าสัมประสิทธิ์เป็นจำนวนเต็มหรือตรรกยะในรูปแบบ x/y

หมายเหตุ for CDD ผู้ใช้: ล ใช้รูปแบบไฟล์เดียวกันกับ CDD. ไฟล์ที่เตรียมไว้สำหรับ
CDD ควรทำงานโดยมีการดัดแปลงเพียงเล็กน้อยหรือไม่มีเลย โปรดทราบว่าตัวแทน V
สอดคล้องกับตัวเลือก "ฮัลล์" ใน CDD. ตัวเลือกเฉพาะสำหรับ CDD สามารถทิ้งไว้ในอินพุต
ไฟล์และจะถูกละเว้นโดย ล. บันทึกไฟล์อินพุตสำหรับ ล ถูกอ่านในรูปแบบอิสระ
หลังเส้น m n มีเหตุผล, ล จะมองหา m*n rationals หรือ integers ที่แยกจากกันอย่างแน่นอน
โดยเว้นวรรค (เว้นว่าง ขึ้นบรรทัดใหม่ แท็บ เป็นต้น) ล จะไม่ "วาง" คอลัมน์พิเศษของ
อินพุตถ้า n น้อยกว่าจำนวนคอลัมน์ที่ให้มา

ขั้นพื้นฐาน Options
เกือบทุกตัวเลือกถูกวางไว้ หลังจาก คำสั่งสุดท้าย รักษาความเข้ากันได้กับ CDD.
หากไม่เป็นเช่นนั้นจะกล่าวไว้โดยชัดแจ้ง

ทุกฐาน ตัวเลือกนี้แนะนำ ล เพื่อแสดงรายการจุดยอดแต่ละจุด (หรือด้าน) สำหรับแต่ละฐาน
เอาท์พุต การทำสำเนา[4].[5] ตัวเลือกนี้มักจะรวมกับ printcobasis

ขอบเขต x ใช้กับตัวแทน H - สำหรับ lrs หรือ nash ไม่ว่าจะเป็นค่าสูงสุดหรือย่อสุด
ควรเลือกตัวเลือก x เป็นจำนวนเต็มหรือตรรกยะ สำหรับการขยายสูงสุด (rep.
การย่อเล็กสุด) ต้นไม้การค้นหาแบบย้อนกลับจะถูกตัดทอนเมื่อใดก็ตามที่มูลค่าวัตถุประสงค์ปัจจุบัน
น้อยกว่า (resp. more) กว่า x.

แคช nล เก็บพจนานุกรม n ล่าสุดไว้ในแผนผังการค้นหาแบบย้อนกลับ มันเร็วขึ้น
ขั้นตอนการย้อนรอย แต่ต้องใช้หน่วยความจำมากขึ้น

การแก้ปัญหา จุดเริ่มต้น ตอนจบพิมพ์ร่องรอยที่คลุมเครือ แต่มีรายละเอียด พจนานุกรม ฯลฯ
เริ่มต้นที่ #B=เริ่มต้นพื้นฐาน และสิ้นสุดที่ #B=สิ้นสุดพื้นฐาน การแก้ปัญหา 0 0 ให้เต็มที่
ติดตาม

ตัวเลข n วางไว้ ก่อน เริ่ม คำสั่ง n คือจำนวนหลักทศนิยมสูงสุดที่จะเป็น
ใช้แล้ว. หากเกินนี้ โปรแกรมจะสิ้นสุดด้วยข้อความ (โดยปกติแล้วจะเป็น
เริ่มใหม่) ค่าเริ่มต้นถูกตั้งไว้ที่ประมาณ 100 หลัก เมื่อสิ้นสุดการทำงานจะมีข้อความคือ
กำหนดให้ผู้ใช้ทราบขนาดจำนวนเต็มสูงสุดที่พบ สามารถใช้เพื่อ
เพิ่มประสิทธิภาพการใช้หน่วยความจำและความเร็วในการรันครั้งต่อๆ ไป (เช่น หากทำการประมาณค่า)

เทอร์โบคู่ หาก lrs ถูกดำเนินการด้วยตัวเลือกขยายใหญ่สุดหรือย่อสุด การค้นหาแบบย้อนกลับ
ต้นไม้ถูกหยั่งรากที่จุดยอดที่เหมาะสมที่สุดสำหรับฟังก์ชันนี้ หากมีหลายค่าที่เหมาะสมที่สุด
จุดยอด ผลลัพธ์มักจะไม่สมบูรณ์ ตัวเลือกนี้ทำให้เกิดการรบกวนเล็กน้อยกับ
วัตถุประสงค์เพื่อหลีกเลี่ยงสิ่งนี้ จะได้รับข้อความเตือนหากพจนานุกรมเริ่มต้นเป็นdual
เสื่อม

ประมาณการ k ประมาณการขนาดเอาต์พุต ใช้ร่วมกับ maxdepth - see
ประมาณการ[6]

ทางเรขาคณิต // ตัวเลือก H-representation หรือ voronoi เท่านั้น // ด้วยตัวเลือกนี้ แต่ละรังสีจะเป็น
พิมพ์พร้อมกับจุดยอดที่เป็นเหตุการณ์ ดูข้อมูลเพิ่มเติมได้ที่
รังสีเรขาคณิตใน คำแนะนำ และ ความคิดเห็น[5].

เหตุการณ์ตัวเลือกนี้จะเปิดโดยอัตโนมัติ พิมพ์โคบาซิส , ดังนั้นดูด้านล่างสำหรับa
คำอธิบายของตัวเลือกนี้ก่อน สามารถใช้กับงานพิมพ์โคบาซิส n. (Ver 4.2b) .PP For
การแสดงแทน H ดัชนีของอสมการอินพุตทั้งหมดที่มีจุดยอด/รังสีที่
กำลังจะถูกส่งออก สำหรับหน้าแบบง่าย ไม่มีผลลัพธ์ใหม่ เนื่องจากดัชนีเหล่านี้
ได้ระบุไว้แล้ว มิฉะนั้น ความไม่เท่าเทียมกันเพิ่มเติมจะแสดงหลังเครื่องหมายทวิภาค
.PP สำหรับอินพุต V-representation ดัชนีของจุดยอด/รังสีอินพุตทั้งหมดที่อยู่บนด้าน
ที่กำลังจะออกฉาย ดัชนีที่ติดดาวแสดงว่าจุดยอดนี้อยู่ใน
cobasis แต่ไม่มีอยู่ในด้าน เกิดจากการยกของที่ใช้
ด้วยอินพุต V-represents

#อุบัติการณ์เช่นเดียวกับการพิมพ์โคบาซิส รวมสำหรับความเข้ากันได้กับ ซีดี

เป็นเส้นตรง k i1i2 i ... ikอินพุตมี k เชิงเส้นในแถว ไอ1ไอ2ไอ ... ikของ
ไฟล์อินพุตเป็นสมการ ดู ลิเนียร์ลิเนียร์[3]

ความลึกสูงสุด k การค้นหาจะถูกตัดทอนที่ระดับความลึก k ฐานทั้งหมดที่มีความลึกน้อยกว่าหรือ
เท่ากับ k จะถูกคำนวณ k เป็นจำนวนเต็มที่ไม่ติดลบ และตัวเลือกนี้ใช้สำหรับ
ประมาณการ - ดู ประมาณการ[6]หมายเหตุ: สำหรับตัวแทน H รังสีที่ความลึก k จะไม่เป็น
รายงาน สำหรับตัวแทน V แง่มุมที่ความลึก k จะไม่ถูกรายงาน

เพิ่ม a0 เอ1... อัน-1 // ตัวแทน H เท่านั้น //

ลด a0 เอ1... อัน-1 // ตัวแทน H เท่านั้น //

หากใช้กับ lrs จุดยอดเริ่มต้นจะเพิ่ม (หรือย่อเล็กสุด) ฟังก์ชัน a0 + a1x1+ ...
+ an-1 xn-1 อาจจำเป็นต้องใช้ตัวเลือก dualperturb เพื่อหลีกเลี่ยงความเสื่อมของคู่ดู Nash
สมดุลและ วัดเชิงเส้น การเขียนโปรแกรม[7]

เอาต์พุตสูงสุด n จำกัดจำนวนเส้นเอาท์พุตที่ผลิต (จุดยอด+รังสีหรือด้าน) เป็น n

เจาะลึก k การย้อนรอยจะสิ้นสุดลงที่ระดับความลึก k สำหรับจำนวนเต็มไม่เป็นลบ นี้
สามารถใช้สำหรับเรียกใช้การค้นหาแบบย้อนกลับบนทรีย่อยเป็นกระบวนการที่แยกจากกัน เช่น ใน a
สภาพแวดล้อมการคำนวณแบบกระจาย

ไม่เป็นลบ // ตัวเลือกนี้ต้องมาก่อนคำสั่ง start// // H-representation only
// Bug: ใช้ได้เฉพาะเมื่อจุดกำเนิดเป็นจุดยอดของรูปทรงหลายเหลี่ยม สำหรับปัญหาที่
อินพุตคือการแสดงแทน H ของรูปแบบ b+Ax>=0, x>=0 (เช่น ตัวแปรทั้งหมด
ไม่เป็นลบ, ความไม่เท่าเทียมกันของข้อจำกัดทั้งหมด) ไม่จำเป็นต้องให้สิ่งที่ไม่เป็นลบ
ข้อจำกัดอย่างชัดเจนหากใช้ตัวเลือกที่ไม่เป็นลบ ไม่สามารถใช้ตัวเลือกนี้สำหรับ
ตัวแทน V หรือด้วยตัวเลือกเชิงเส้น (ซึ่งในกรณีนี้ เชิงเส้นจะเป็น
ถือเป็นความไม่เท่าเทียมกัน) ตัวเลือกนี้อาจใช้กับ redund แต่โดยนัย
ข้อจำกัด nonnegativity ไม่ได้ถูกทดสอบตัวเองเพื่อความซ้ำซ้อน เพื่อทดสอบทุกอย่างมัน
จำเป็นต้องป้อนข้อจำกัด nonnegativity อย่างชัดเจนในไฟล์อินพุต (ในเวอร์ชั่น
4.1 จุดกำเนิดต้องเป็นจุดยอด)

พิมพ์โคบาซิส k;แก้ไขใน lrs 4.0 พิมพ์ cobasis ทุก k'th ถ้า k ถูกละไว้
cobasis ถูกพิมพ์สำหรับแต่ละจุดยอด/รังสี/ด้านที่ส่งออก มีประโยชน์ในระยะยาว
เพื่อพิมพ์ cobasis เป็นครั้งคราวเพื่อให้สามารถเริ่มโปรแกรมใหม่ได้หากจำเป็น
ตัวแทน H: หากอินพุตเป็นตัวแทน H ค่า cobasis จะเป็นรายการดัชนีของ
ความไม่เท่าเทียมกันจากไฟล์อินพุตที่กำหนดจุดยอดหรือรังสีปัจจุบัน ดูตัวเลือก
เหตุการณ์ ด้านบนสำหรับข้อมูลเพิ่มเติม สำหรับรังสีจะมีการพิมพ์ cobasis ในกรณีนี้
cobasis คือ cobasis ของจุดยอดที่รังสีเล็ดลอดออกมา หนึ่งในดัชนี
ติดดาว ซึ่งบ่งชี้ถึงความไม่เท่าเทียมกันที่จะถูกละทิ้งจาก cobasis เพื่อกำหนด
เรย์ อีกทางหนึ่ง ถ้า ทุกฐานใช้ตัวเลือก โคเบสทั้งหมดจะถูกพิมพ์ออกมา
ตัวแทน V: ถ้าอินพุตเป็นตัวแทน V cobasis คือรายการของอินพุต
จุดยอด / รังสีที่กำหนดด้านปัจจุบัน ดูตัวเลือก เหตุการณ์ ด้านบนสำหรับเพิ่มเติม
ข้อมูล. ที่จะเริ่มต้น ล จากด้านนี้ต้องให้ทั้ง 4 ดัชนีตามลำดับ
(ละเว้น *)

พิมพ์หย่อน ใหม่ในเวอร์ชั่น 4.2 ; // ใช้กับตัวแทน H // lrs พิมพ์รายการของ
ดัชนีของความไม่เท่าเทียมกันของอินพุตที่ได้รับความพึงพอใจอย่างเคร่งครัดสำหรับจุดยอดปัจจุบันคือ
ตัวแปรหย่อนที่สอดคล้องกันเป็นค่าบวก หากมีการตั้งค่า nonnegative รายการก็จะ
รวมดัชนี n+i สำหรับแต่ละตัวแปรการตัดสินใจ xi ซึ่งเป็นค่าบวก โครงการ ใช้โดย
lrsfourier[8] เท่านั้น

การเริ่มต้นใหม่ V# R# B# ความลึก {แง่มุม #s or จุดยอด/เรย์ #s} แก้ไขใน lrs4.0 ล เป็นไปได้
เริ่มต้นใหม่จาก cobasis ที่รู้จัก การคำนวณจะดำเนินการยุติตามปกติ ทั้งหมด
ของข้อมูลอยู่ในผลลัพธ์จาก a พิมพ์โคบาซิส ตัวเลือก ใบสั่ง of
ดัชนี is มาก สำคัญ, ป้อนให้ตรงตามที่ปรากฏในผลลัพธ์จาก
ก่อนหน้านี้ยกเลิกการทำงาน

เริ่มต้น cobasis ไอ1ไอ2ไอ ... ใน -1 ซึ่งช่วยให้ผู้ใช้สามารถระบุ cobasis ที่รู้จักสำหรับ
เริ่มต้นการค้นหาแบบย้อนกลับ ไอ1ไอ2ไอ ... ใน -1 เป็นรายการความไม่เท่าเทียมกัน (for
การแสดงแทน H) หรือจุดยอด/รังสี (สำหรับการแทนค่า V) ที่กำหนด cobasis ถ้ามันเป็น
ไม่ถูกต้อง หรือไม่ได้ระบุตัวเลือกนี้ ล จะพบ cobasis เริ่มต้นของตัวเอง NS
ต้นไม้การค้นหาแบบย้อนกลับจะถูกตัดทอน (ตัด) เมื่อใดก็ตามที่พบจุดสุดยอดใหม่ หมายเหตุ: นี้
จำเป็นต้องสร้างชุดของจุดยอดทั้งหมดที่อยู่ติดกับจุดสุดยอดที่เหมาะสมใน
รูปทรงหลายเหลี่ยม แต่เป็นเพียงส่วนย่อยของพวกมัน

ละเอียดพิมพ์ข้อมูลรายละเอียดเพิ่มเติมเล็กน้อยเกี่ยวกับการวิ่ง

ปริมาณ // V-representation เท่านั้น // คำนวณปริมาตร - ดูหัวข้อ ปริมาณ การคำนวณ[9]

โวโรนอย // V-representation เท่านั้น - วางหลังคำสั่ง end // Compute
แผนภาพโวโรนอย - ดูหัวข้อ โวโรน้อย ไดอะแกรม[10]

หมายเหตุ

1. หน้าคำถามที่พบบ่อย
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2.cdd
http://www.cs.mcgill.ca/%7เอฟุกุดะ/ซอฟท์/cdd_home/cdd.html

3. ความเป็นเส้นตรง
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#เส้นตรง

4. การทำสำเนาเอาต์พุต
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20การทำซ้ำ

5.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hints%20and%20ความคิดเห็น

6. การประมาณการ
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#การประมาณค่า

7. การเขียนโปรแกรมเชิงเส้น
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20การเขียนโปรแกรม

8. อิลร์ฟูริเยร์
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#ฟูเรียร์

9. การคำนวณปริมาณ
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20การคำนวณ

10. โวโรนอยไดอะแกรม
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20ไดอะแกรม

ใช้ lrsfourier ออนไลน์โดยใช้บริการ onworks.net