lrsfourier - آنلاین در ابر

برنامه:

نام

lrslib - تبدیل بین بازنمایی های چندوجهی محدب.

خلاصه

lrs input.ine

lrs input.ine | lrsbuffer

lrsfourier file.ine [پرونده کردن]

اضافی input.ine

شرح

یک چند وجهی را می توان با فهرستی از نابرابری ها توصیف کرد (نمایش H) یا طبق یک لیست
از رئوس و پرتوهای شدید آن (نمایش V). lrs یک برنامه C است که a را تبدیل می کند
نمایش H یک چند وجهی به نمایش V آن و بالعکس. این مسایل
به ترتیب در راس شمارش و محدب پوست مشکلات.

فوکودا پاسخ به برخی سوالات مهم با ما[1] شامل مقدمه مفصل تری برای مسئله، همراه با
بسیاری از نکات مفید برای کاربر جدید

lrsbuffer می تواند برخی از خروجی های تکراری را حذف کند. اضافی نابرابری های اضافی را در
ورودی

فایل فرمها

فرمت های فایل به طور مشترک با Komei Fukuda توسعه یافته و با آن سازگار است سی دی[2].

ورودی برای lrs یک نمایش H یا V از یک پلی توپ است.

نام
{خط نمایندگی}
{گزینه ها}
{خطی ها[3]}
شروع
mn منطقی
{ماتریس ورودی}
پایان
{گزینه ها}

نام یک نام ارائه شده توسط کاربر برای پلی توپ است. نظرات ممکن است قبل از شروع یا ظاهر شوند
پس از پایان، و برای جلوگیری از تفسیر به عنوان یک گزینه، باید با خاص شروع شود
کاراکتری مانند "*" یا "#".

نام یک نام ارائه شده توسط کاربر برای پلی توپ است. نمایندگی خط است یا
"H-representation" یا "V-representation". اگر حذف شود، نمایش H فرض می شود. در
ضرایب ورودی در قالب آزاد خوانده می شوند و از نظر نوع بررسی نمی شوند. ضرایب هستند
با فضای سفید جدا شده است. m تعداد سطرها و n تعداد ستون های ورودی است
ماتریس

نمایش H
عدد صحیح m تعداد نابرابری ها و عدد صحیح n بعد از است
ورودی +1. فهرستی از نابرابری ها حاوی ضرایب نابرابری های فرم است

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

این نابرابری به عنوان خط ورودی است

a0 a1... an-1

ضرایب را می توان به صورت اعداد صحیح یا منطقی در قالب x/y وارد کرد.

نمایش V
عدد صحیح m تعداد رئوس و پرتوها و عدد صحیح n بعد
ورودی +1. هر رأس در فرم آورده شده است

1 v0 v 1... vn-1

هر پرتو در فرم داده شده است

0 r0 r 1... rn-1

جایی که r0 r 1... rn-1 یک نقطه روی پرتو است.

در هر فایل باید حداقل یک راس وجود داشته باشد. برای چندوجهی محدود وجود نخواهد داشت
اشعه وارد شد ضرایب را می توان به صورت اعداد صحیح یا منطقی در قالب x/y وارد کرد.

توجه داشته باشید برای سی دی کاربران: lrs اساسا از همان فرمت فایل استفاده می کند سی دی. فایل های آماده شده برای
سی دی باید با کمی تغییر یا بدون تغییر کار کند. توجه داشته باشید که نمایش V
مربوط به گزینه "Hull" در است سی دی. گزینه های خاص برای سی دی را می توان در ورودی گذاشت
فایل ها و نادیده گرفته می شوند lrs. به فایل های ورودی برای lrs به صورت رایگان خوانده می شوند،
بعد از خط m n منطقی, lrs دقیقاً m*n گویا یا اعداد صحیح جدا شده را جستجو می کند
با فضای سفید (خالی، بازگشت کالسکه، زبانه و غیره). lrs ستون‌های اضافی را رها نمی‌کند
ورودی اگر n کمتر از تعداد ستون های ارائه شده باشد.

اساسی گزینه
تقریباً همه گزینه ها قرار داده شده اند بعد از بیانیه پایانی، حفظ سازگاری با سی دی.
در مواردی که چنین نیست، به صراحت ذکر خواهد شد.

همه پایه ها این گزینه دستور می دهد lrs برای فهرست کردن هر رأس (یا وجه) برای هر یک از پایه های آن.
تولید تکثیر. مضاعف شدن[4].[5] این گزینه اغلب با printcobasis ترکیب می شود.

بسته x با نمایش H استفاده کنید - برای lrs یا nash یا به حداکثر رساندن یا به حداقل رساندن
گزینه باید انتخاب شود x یک عدد صحیح یا گویا است. برای به حداکثر رساندن (resp.
به حداقل رساندن) درخت جستجوی معکوس هر زمان که مقدار هدف فعلی کوتاه می شود
کمتر (به عبارت دیگر بیشتر) از x است.

نهانگاه nlrs آخرین n دیکشنری را در درخت جستجوی معکوس ذخیره می کند. این سرعت می گیرد
مرحله عقبگرد است، اما به حافظه بیشتری نیاز دارد.

اشکال زدایی کردن پایه شروع پایه پایانیردیابی مرموز اما مفصل، لغت نامه ها و غیره را چاپ کنید.
از #B=startingbasis شروع می شود و در #B=endingbasis ختم می شود. اشکال زدایی کردن 0 0 کامل می دهد
پی گیری.

رقم n قرار داده شده قبل از la شروع بیانیه n حداکثر تعداد ارقام اعشاری است
استفاده شده. اگر از این مقدار بیشتر شود، برنامه با یک پیام خاتمه می یابد (معمولاً می تواند باشد
دوباره راه اندازی شد). پیش فرض روی 100 رقم تنظیم شده است. در پایان اجرا یک پیام است
با توجه به اطلاع کاربر از حداکثر اندازه صحیحی که با آن مواجه شده است. این ممکن است مورد استفاده قرار گیرد
استفاده از حافظه و سرعت را در اجراهای بعدی بهینه کنید (اگر برای مثال در حال انجام تخمین هستید).

dualperturb اگر lrs با گزینه maximize یا minimize اجرا شود، جستجوی معکوس انجام می شود
درخت در یک راس بهینه برای این تابع ریشه دارد. اگر چند بهینه وجود داشته باشد
رئوس، خروجی اغلب کامل نخواهد بود. این گزینه یک اغتشاش کوچک به
هدف اجتناب از این اگر فرهنگ لغت شروع دوتایی باشد، یک پیام هشدار داده می شود
انحطاط

تخمین می زند k اندازه خروجی را تخمین بزنید. در ارتباط با حداکثر عمق استفاده می شود - ببینید
برآورد کردن.[6]

هندسی // فقط گزینه H-representation یا voronoi // با این گزینه هر پرتو است
همراه با راس که با آن برخورد می کند چاپ می شود. برای اطلاعات بیشتر ببین
پرتوهای هندسی در نکات و نظرات[5]

وقوعاین گزینه به طور خودکار روشن می شود printcobasis ، بنابراین زیر را ببینید
ابتدا توضیح این گزینه قابل استفاده با printcobasis n. (نسخه 4.2b) .PP برای
نمایش H ورودی، شاخص‌های همه نابرابری‌های ورودی که حاوی رأس/پرتو هستند
در شرف خروجی است برای یک چهره ساده، از این شاخص ها، خروجی جدیدی وجود ندارد
قبلاً فهرست شده اند. در غیر این صورت، نابرابری‌های تنگ اضافی بعد از دو نقطه فهرست می‌شوند.
.PP برای نمایش V ورودی، شاخص‌های همه رئوس/اشعه‌های ورودی که روی وجه قرار دارند
که در شرف خروجی است. یک شاخص ستاره دار نشان می دهد که این راس نیز در قسمت است
cobasis، اما در وجه موجود نیست. این به دلیل عملیات بلند کردن استفاده می شود
با نمایش های V ورودی.

#وقوعهمان printcobasis. برای سازگاری با cdd

خطی بودن k i1i2 i ... ikورودی حاوی k خطی در ردیف است i1i2i ... ikاز
فایل ورودی معادلات هستند. دیدن خطی ها[3]

بیشترین عمق k جستجو در عمق k کوتاه خواهد شد. همه پایه های با عمق کمتر از یا
برابر k محاسبه خواهد شد. k یک عدد صحیح غیر منفی است و این گزینه برای استفاده می شود
برآوردها - ببینید برآورد کردن.[6]توجه داشته باشید: برای نمایش های H، پرتوهای در عمق k نخواهند بود
گزارش شده است. برای نمایش های V، وجوه در عمق k گزارش نمی شود.

به حداکثر رساندن a0 a1 ... an-1 // فقط نمایش H //

به حداقل رساندن a0 a1 ... an-1 // فقط نمایش H //

اگر با lrs استفاده شود، راس شروع تابع a0 + a1x1+ را بیشینه می کند (یا کمینه می کند).
+ an-1 xn-1. گزینه dualperturb ممکن است برای جلوگیری از انحطاط دوگانه مورد نیاز باشد. به Nash مراجعه کنید
تعادل و خطی برنامه نويسي[7]

حداکثر خروجی n تعداد خطوط خروجی تولید شده (اعم از رئوس + اشعه یا وجه) را به n محدود می کند

ذهنیت k عقبگرد در عمق k برای عدد صحیح غیر منفی ka خاتمه می یابد. این
می تواند برای اجرای جستجوی معکوس در زیر درختان به عنوان فرآیندهای جداگانه استفاده شود، به عنوان مثال در a
محیط محاسباتی توزیع شده

غیر منفی // این گزینه باید قبل از دستور start// //H-representation فقط بیاید
// اشکال: فقط در صورتی می توان از آن استفاده کرد که مبدأ یک رأس چند وجهی باشد برای مشکلاتی که در آن
ورودی یک نمایش H به شکل b+Ax>=0، x>=0 است (یعنی همه متغیرها
غیر منفی، همه محدودیت ها نابرابری) لازم نیست غیر منفی داده شود.
در صورت استفاده از گزینه غیرمنفی، صراحتاً محدودیت ایجاد می کند. از این گزینه نمی توان استفاده کرد
V-representations یا با گزینه linearity (در این صورت خطی ها خواهند بود
به عنوان نابرابری در نظر گرفته می شود). این گزینه ممکن است با redund استفاده شود، اما ضمنی
محدودیت های غیر منفی خود برای افزونگی آزمایش نمی شوند. برای تست همه چیز آن
برای وارد کردن قیود غیر منفی به طور صریح در فایل ورودی ضروری است. (در نسخه
4.1، مبدا باید یک راس باشد).

printcobasis k;اصلاح شده در lrs 4.0 هر k'th cobasis چاپ می شود. اگر k حذف شود،
cobasis برای هر رأس / پرتو / وجهی که خروجی می شود چاپ می شود. برای طولانی مدت مفید است
گهگاهی کوباسیس را چاپ کنید تا در صورت لزوم برنامه مجدداً راه اندازی شود.
نمایش H: اگر ورودی یک نمایش H باشد، cobasis فهرستی از شاخص‌ها است
نابرابری های فایل ورودی که راس یا پرتو فعلی را تعریف می کند. گزینه را ببینید
وقوع برای اطلاعات بیشتر در بالا برای پرتوها نیز یک کوباسیس چاپ می شود. در این مورد
cobasis کوباسیس رأسی است که پرتو از آن خارج می شود. یکی از شاخص ها
ستاره دار است، این نشان دهنده نابرابری است که باید از cobasis حذف شود تا تعریف شود
اشعه. متناوبا، اگر همه پایه هااز گزینه استفاده می شود، همه کوبیس ها چاپ می شوند.
نمایش V: اگر ورودی یک نمایش V باشد، cobasis لیستی از ورودی است
رئوس / پرتوهایی که وجه فعلی را تعریف می کنند. گزینه را ببینید وقوع در بالا برای اطلاعات بیشتر
اطلاعات برای شروع lrs از این جنبه، هر 4 شاخص باید به این ترتیب داده شوند
(* را حذف کنید).

شلوار چاپ جدید در نسخه 4.2; // استفاده با H-representation // lrs لیستی از موارد را چاپ می کند
شاخص‌های نابرابری‌های ورودی که دقیقاً برای راس جاری برآورده می‌شوند، یعنی.
متغیر Slack مربوطه مثبت است. اگر غیرمنفی تنظیم شود، لیست نیز تنظیم می شود
شامل شاخص های n+i برای هر متغیر تصمیم گیری xi که مثبت است. پروژه استفاده شده توسط
lrsfourier[8] فقط.

شروع دوباره V# R# B# عمق {وجه #s or راس / پرتو #s} در lrs4.0 اصلاح شده است lrs می تواند
از هر کوباسی شناخته شده ای دوباره شروع شد. محاسبه به خاتمه عادی ادامه خواهد داد. همه
از اطلاعات موجود در خروجی از a printcobasis گزینه. سفارش of
la شاخص is بسیار مهم، آنها را دقیقاً همانطور که در خروجی ظاهر می شوند وارد کنید
اجرا قبلی سقط شده

startingcobasis i1i2i ... در 1 این به کاربر اجازه می دهد تا یک cobasis شناخته شده را برای آن مشخص کند
شروع جستجوی معکوس i1i2i ... در 1 فهرستی از نابرابری ها (برای
نمایش H) یا رئوس/پرتوها (برای نمایش V) که یک cobasis را تعریف می کنند. اگر هست
نامعتبر است، یا این گزینه مشخص نشده است، lrs cobasis شروع خود را پیدا خواهد کرد. در
درخت جستجوی معکوس هر زمان که با راس جدیدی مواجه می شود کوتاه می شود (هرس می شود). توجه: این
توجه داشته باشید که لزوما مجموعه ای از تمام رئوس مجاور راس بهینه را تولید می کند
چند وجهی، اما فقط زیر مجموعه ای از آنها.

واژگاناطلاعات کمی دقیق تر در مورد اجرا چاپ کنید.

حجم // فقط نمایش V // محاسبه حجم - بخش را ببینید حجم محاسبات.[9]

ورونوی // فقط V-representation - بلافاصله بعد از دستور پایان قرار دهید // محاسبه
نمودار ورونوی - بخش را ببینید ورونوی نمودارها[10]

NOTES

1. صفحه پرسش و پاسخ
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2. سی دی
http://www.cs.mcgill.ca/%7Efukuda/soft/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%20Duplication

5.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hints%20and%20Comments

6. برآورد.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation

7. برنامه ریزی خطی
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#برنامه‌نویسی خطی%20

8. lrsfourier
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#fourier

9. محاسبه حجم.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation

10. نمودارهای ورونوی.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagrams

با استفاده از خدمات onworks.net از lrsfourier به صورت آنلاین استفاده کنید