问题标签 [greedy]

我正在使用 html 框架源自动下载许多图像。太棒了，Sed，wget。帧源示例：

所以我这样做：

得到看起来像这样的部分：

然后这样做：

wget --base=/some/url/concept_Core.jpg

但是有一条讨厌的线。那条线，很明显，是网站中的一个错误，或者任何可能的错误，但它是错误的，但是我无法更改它。;)

即，将其中的两个“ concept_Frgate16.jpg ”排成一行。我的剧本给了我

你明白为什么。Sed 是贪婪的，这显然出现在这种情况下。

现在的问题是，我该如何摆脱这种极端情况？也就是说，让它不贪婪，让它停在第一个.jpg 上？强调文本

问题应该具有哪些属性，以便我可以决定使用动态编程或贪婪方法的方法？

我想在 IIS 7.5（在 Windows Web Server 2008 R2 上）中创建一个通用的 URL 重写规则。

我想匹配以下网址：

www.mysite.com/param
www.mysite.com/folder1/
www.mysite.com/folder1/param
www.mysite.com/folder1/folder2/
www.mysite.com/folder1/folder2/param

当我想匹配一个文件夹时，请注意尾部的斜杠 (/)，否则它是一个参数。

我已经设置了以下重写规则：

它具有三个匹配子句：{R:1}、{R:2} 和 {R:3}。但是，当我输入以下测试 URL 时：

文件夹 1/参数

我得到以下回复：

{R:1} 为空
{R:2} = 文件夹
1 {R:3} = 参数

我怀疑以下反应：

{R:1} = 文件夹 1
{R:2} 为空
{R:3} = 参数

即我希望将folder1映射到重写模式的第一部分。

我想将重写规则映射到：

我缺少什么让匹配变得贪婪，即匹配第一个可能的子句？

我正在使用 Java 进行图形着色项目。我需要使用四色定理实现四种不同的图形着色算法。我对名为少数邻居贪婪算法的算法之一有疑问。

我有一张地图，其中包含一堆多边形对象（存储在数组列表中）。另外，我有一个 2D 布尔数组，它表示不同多边形的邻接关系。

我从理论上知道该算法：我有一个优先级队列来存储我的未着色多边形。基于邻接计数的队列顺序。如果一个多边形的邻居很少，它被认为比一个有很多邻居的多边形好。无论如何，该算法应该重复从优先队列中绘制一个多边形，并尝试根据它的邻接对其进行着色。

不幸的是，我在实施部分遇到了问题。我根据邻接计数获得了优先队列，但是在为这些多边形分配颜色时遇到了问题。如果有人研究过这种算法，或者有想法的人，请与我分享。我需要一些想法来加快实施部分。

提前致谢。

我的 ANTLR 语法中有这样的规则：

此规则仅匹配 c 样式的注释，因此它可以接受任何一对 /* 和 */ 以及介于两者之间的任意文本，并且它工作正常。

我现在要做的是在规则匹配时捕获 /* 和 */ 之间的所有文本，以使其可供操作访问。像这样的东西：

这种方法不起作用，在解析过程中它在到达“/ *”之后的第一个字符时给出“没有可行的选择”

我不太清楚是否/如何做到这一点 - 欢迎任何建议或指导，谢谢。

我想

成为

为了实现这一点，我做到了

但是，这个正则表达式改变了

进入

代替

有人可以帮我建立一个改变的正则表达式

进入

我正在使用 Java 正则表达式来匹配和捕获字符串，例如：

0::10000

一个解决方案是：

(0::\d{1,8})

但是，输入的匹配会成功

10::10000

同样，这是错误的。因此，我现在有：

[^\d](0::\d{1,8})

这意味着它必须以除数字以外的任何字符开头，但这意味着在第一个零之前需要有一些字符。我真正想要的（以及我需要帮助的）是说“以非数字或根本没有的方式领导”。

总之，最终解决方案正则表达式应匹配以下内容：

0::10000
kjkj0::10000

并且不应与以下内容匹配：

10::10000

如果有人想提供帮助，这个网站可能会有用。

谢谢。

我对正则表达式相当有经验，但是在当前涉及析取的应用程序中遇到了一些困难。

我的情况是这样的：我需要根据地址的“标识符元素”上的正则表达式匹配将地址分成其组成部分——类似的英文示例是“state”、“road”或“林荫大道”--例如，如果我们在地址中写下了这些。想象一下，我们有一个像下面这样的地址，其中（这在英语中永远不会发生），我们在每个名称之后指定了标识符类型

United States COUNTRY California STATE San Francisco CITY Mission STREET 345 NUMBER

（大写字母中的词是我所说的“标识符”）。

我们想把它解析成：
United States COUNTRY
California STATE
San Francisco CITY
Mission STREET
245 NUMBER


好的，这当然是为英语设计的，但有一个问题：我正在处理中文数据，实际上这种标识符规范一直在发生。下面的一个例子：

云南-省 ; 丽江-市 ; 古城-区 ; 西安-街 ; 杨春-巷 ; Yunnan-Province ; LiJiang-City ; GuCheng-District ; Xi'An-Street ; Yangchun-Alley

这很容易——对潜在的候选标识符名称进行惰性匹配，分成一个分离列表。

对于中国，以下是“省级”实体：

省 (Province) , 自治区 (Autonomous Region) , 市 (Municipality)

所以到目前为止我的正则表达式看起来像这样：

(.+?(?:(?:省)|(?:自治区)|(?:市)))

我有一系列这些，以说明地址的不同部分。例如，对应于城市的下一个级别是：

(.+?(?:(?:地区)|(?:自治州)|(?:市)|(?:盟)))

所以要匹配一个省实体，然后是一个城市实体：

(.+?(?:(?:省)|(?:自治区)|(?:市)))(.+?(?:(?:地区)|(?:自治州)|(?:市)|(?:盟)))

使用命名的捕获组：
(?<Province>.+?(?:(?:省)|(?:自治区)|(?:市)))(?<City>.+?(?:(?:地区)|(?:自治州)|(?:市)|(?:盟)))

对于上述情况，这会产生：
$+{Province} = 云南省<br> $+{City} = 丽江市

这一切都很好，让我走得很远。然而，问题是当我尝试考虑可能是其他标识符的子字符串的标识符时。例如，一个常见的街道实体是“村委会”，意思是村组委会。在我希望分开的一组地址中，并非每个地址都完整地写出。事实上，我找到了“村委”，也只是简单的“村”。

问题？如果我对这些元素进行纯析取，我们有以下内容：

(?<Street>.+?(?:(?:村委会)|(?:村委)|(?:村)))

然而，如果你有一个实体保定-村委会（保定村组委会），这个懒惰的正则表达式会在村停下来收工，让我们可怜的委员会成为孤儿，因为村是潜在的分离元素之一.

想象一下这样的英语等价物：
(?<Animal>.+?(?:(?:Cat)|(?:Elephant)|(?:CatElephant)|(?:City)))

我们有两个输入字符串：
1.“crap catelephant crap city”，我们想要“Crap catelephant”和“crap city” 2.“crap catelephant city”，我们想要“crap cat”“elephant city”

啊，你说的解决办法就是让前置标识符贪婪捕获。但！有些实体具有相同的标识符但不在同一级别。

以市为例。这意味着简单的“城市”。但在中国，有县级市、省级市和市级市。如果该字符在字符串中出现两次，尤其是在两个相邻实体中，贪心搜索会错误地将贪心匹配标记为第一个实体。如下所示：

广东-省 ; 江门-市 ; 开平-市 ; 三埠-区 石海管-区<br> Guangdong-province ; Jiangmen-City ; Kaiping-City ; Sanbu-District ; Shihaiguan-District

（请注意，如上所述，这是手动分割的。原始数据将仅包含一串连接的字符）

贪婪搜索的匹配是
江门市开平市

这是错误的，因为两个相邻的实体应该被分成它们的组成部分。一个是省级市，一个是县级市。

回到原点，感谢您阅读本文，有没有办法对析取实体进行加权？我希望正则表达式首先找到最高的“加权”标识符。村委会而不是简单的村，例如“catelephant”而不是“cat”。在初步实验中，正则表达式解析器显然从左到右寻找析取匹配。这是一个有效的假设吗？我应该将最常出现的标识符放在分离列表的首位吗？

如果我失去了任何与中国相关的细节，我很抱歉，如果需要可以进一步澄清。这个例子真的不必是中文的——我认为更一般地说，这是一个关于正则表达式分离匹配机制的问题——它优先选择分离实体的顺序，以及它如何决定何时“调用它”一天”在懒惰搜索的背景下？

在某种程度上，在懒惰和贪婪搜索之间是否存在某种中间立场？在最长/最高加权分离实体之前找到你能找到的最小位？懒惰，但如果可以的话，为了彻底而付出一点额外的努力？（顺便问一下，我大学的工作理念？）

贪心算法有什么用？一个真实的例子？

自从昨天站在超市的销售点，再次尝试启发式地找到我的硬币的最佳分区，同时试图忽略我身后不耐烦和紧张的队列，我一直在思考潜在的算法问题：

给定一个价值为 v ₁ ,...,v _n的硬币系统，有限数量的硬币 a ₁ ,...,a _n以及我们需要支付的金额 s。我们正在寻找一种算法来计算分区 x ₁ ,...,x _n (with 0<=x _i <=a _i ) with x ₁ *v ₁ +x ₂ *v ₂ +...+x _n *v _n >= s 使得总和 x ₁ +...+x _n - R(r) 最大化，其中 r 是变化，即 r = x ₁ *v ₁ +x ₂ *v ₂ +。 ..+x_n *v _n - s 和 R(r) 是从收银员返回的硬币数量。我们假设收银员拥有无限数量的所有硬币，并且总是返还最少数量的硬币（例如使用 SCHOENING 等人解释的贪婪算法）。我们还需要确保没有换钱，所以最好的解决方案不是简单地给所有的钱（因为在这种情况下解决方案总是最优的）。

感谢您的创意输入！